Usbrth

What is the padding with red substance inside of steak packaging?

Homework question about an engine pulling a train

Why not take a picture of a closer black hole?

How to handle characters who are more educated than the author?

What to do when moving next to a bird sanctuary with a loosely-domesticated cat?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

Nested ellipses in tikzpicture: Chomsky hierarchy

Huge performance difference of the command find with and without using %M option to show permissions

Intergalactic human space ship encounters another ship, character gets shunted off beyond known universe, reality starts collapsing

Drawing vertical/oblique lines in Metrical tree (tikz-qtree, tipa)

What's the point in a preamp?

How do you keep chess fun when your opponent constantly beats you?

Is 'stolen' appropriate word?

Why don't hard Brexiteers insist on a hard border to prevent illegal immigration after Brexit?

Accepted by European university, rejected by all American ones I applied to? Possible reasons?

What other Star Trek series did the main TNG cast show up in?

Can the Right Ascension and Argument of Perigee of a spacecraft's orbit keep varying by themselves with time?

Student Loan from years ago pops up and is taking my salary

Single author papers against my advisor's will?

What does Linus Torvalds mean when he says that Git "never ever" tracks a file?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

What happens to a Warlock's expended Spell Slots when they gain a Level?

The following signatures were invalid: EXPKEYSIG 1397BC53640DB551

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

Do the primal and dual have the same number of basic variables

1

$begingroup$

For the primal problem with constraints $Axleq b$ and the dual problem with constraints $A^Tygeq c$. Since $rank(A) = rank(A^T)$, does this mean that the primal and dual will always have the same number of basic variables?

optimization linear-programming

share|cite|improve this question

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The number of basics is equal to the number of rows (constraints).
  $endgroup$
  – Erwin Kalvelagen
  Nov 13 '17 at 20:43
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your question does not answer the question that I asked, and has only further confused me. Unfortunately, your comment has not been very helpful. Could you submit a proof?
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:00
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In any LP with $n$ columns and $m$ rows, there will be $m$ basics. The primal and the dual are just different LPs.
  $endgroup$
  – Erwin Kalvelagen
  Nov 13 '17 at 21:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  And also, my understanding is that with no redundant constraints in the primal $Axleq b$, we will have $rank(A)=mleq n$ and so of course, the number of basic variables in the primal will be equal to the number of rows, $m$
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Suppose we have a matrix $A$ that is $mtimes n$ and $ngeq m$. Then assuming no redundant constraints, there are $m$ basic variables. The dual is defined $A^Tygeq c$ and has $n$ rows but $rank(A^T)=m$. So we can only construct an $mtimes m$ basis matrix for the dual. Thus the dual must have $m$ basic variables. Am I missing something? How can the dual have $n$ basic variables in this case, as you say? As the basis matrix must be invertible, wouldn't this necessitate an $ntimes n$ basis matrix?
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:13
  
  

  
  
  
  

 | 
show 1 more comment

1

$begingroup$

For the primal problem with constraints $Axleq b$ and the dual problem with constraints $A^Tygeq c$. Since $rank(A) = rank(A^T)$, does this mean that the primal and dual will always have the same number of basic variables?

optimization linear-programming

share|cite|improve this question

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The number of basics is equal to the number of rows (constraints).
  $endgroup$
  – Erwin Kalvelagen
  Nov 13 '17 at 20:43
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your question does not answer the question that I asked, and has only further confused me. Unfortunately, your comment has not been very helpful. Could you submit a proof?
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:00
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  In any LP with $n$ columns and $m$ rows, there will be $m$ basics. The primal and the dual are just different LPs.
  $endgroup$
  – Erwin Kalvelagen
  Nov 13 '17 at 21:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  And also, my understanding is that with no redundant constraints in the primal $Axleq b$, we will have $rank(A)=mleq n$ and so of course, the number of basic variables in the primal will be equal to the number of rows, $m$
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Suppose we have a matrix $A$ that is $mtimes n$ and $ngeq m$. Then assuming no redundant constraints, there are $m$ basic variables. The dual is defined $A^Tygeq c$ and has $n$ rows but $rank(A^T)=m$. So we can only construct an $mtimes m$ basis matrix for the dual. Thus the dual must have $m$ basic variables. Am I missing something? How can the dual have $n$ basic variables in this case, as you say? As the basis matrix must be invertible, wouldn't this necessitate an $ntimes n$ basis matrix?
  $endgroup$
  – UnchartedWaters
  Nov 13 '17 at 21:13
  
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

For the primal problem with constraints $Axleq b$ and the dual problem with constraints $A^Tygeq c$. Since $rank(A) = rank(A^T)$, does this mean that the primal and dual will always have the same number of basic variables?

optimization linear-programming

share|cite|improve this question

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

$endgroup$

share|cite|improve this question

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

share|cite|improve this question

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

asked Nov 13 '17 at 19:53

UnchartedWatersUnchartedWaters

103

1 Answer
1

active

oldest

votes

0

$begingroup$

The confusion here stems from the fact that you must first convert the primal and dual forms to one with equality constraints (because this is required when talking about basic feasible solutions.)

Suppose we are dealing with a maximization primal.

The inequality constraint $Ax leq b$ can be projected into a higher space by adding slack variables $u$ to get an equality constraint, $$Ax + u = b.$$ Note that $x geq 0, u geq 0$. Thus the actual matrix we're looking at is $[A I]$, of dimension $m times (m + n)$. The rank of this 'primal' matrix is the rank of $A$, so $m$. So, the primal has $m$ basic variables.

The dual of this has the feasible region $A^T y geq c$ where $y geq 0$. However, we need to convert this to an equality constraint too! Add slack variables $s$ to get $$ A^T y - s = c $$ where $y geq 0, s geq 0$.
Note that the matrix we're dealing with in the dual is now $[A^T -I]$, of dimension $n times (m + n)$. This is not the transpose (or the negative of the transpose, even if $-I$ were $I$.) of the 'primal' matrix, because the dimensions don't match! You can see that the rank of this matrix is $n$, because of the rows of the identity matrix. So, the dual has $n$ basic variables.

Thus, if $m neq n$, the dual and primal have a different number of basic variables.

share|cite|improve this answer

edited 2 days ago

answered Apr 7 at 20:22

AmeyaAmeya

113

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2518806%2fdo-the-primal-and-dual-have-the-same-number-of-basic-variables%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

The confusion here stems from the fact that you must first convert the primal and dual forms to one with equality constraints (because this is required when talking about basic feasible solutions.)

Suppose we are dealing with a maximization primal.

The inequality constraint $Ax leq b$ can be projected into a higher space by adding slack variables $u$ to get an equality constraint, $$Ax + u = b.$$ Note that $x geq 0, u geq 0$. Thus the actual matrix we're looking at is $[A I]$, of dimension $m times (m + n)$. The rank of this 'primal' matrix is the rank of $A$, so $m$. So, the primal has $m$ basic variables.

The dual of this has the feasible region $A^T y geq c$ where $y geq 0$. However, we need to convert this to an equality constraint too! Add slack variables $s$ to get $$ A^T y - s = c $$ where $y geq 0, s geq 0$.
Note that the matrix we're dealing with in the dual is now $[A^T -I]$, of dimension $n times (m + n)$. This is not the transpose (or the negative of the transpose, even if $-I$ were $I$.) of the 'primal' matrix, because the dimensions don't match! You can see that the rank of this matrix is $n$, because of the rows of the identity matrix. So, the dual has $n$ basic variables.

Thus, if $m neq n$, the dual and primal have a different number of basic variables.

share|cite|improve this answer

edited 2 days ago

answered Apr 7 at 20:22

AmeyaAmeya

113

$endgroup$

add a comment | 

0

$begingroup$

The confusion here stems from the fact that you must first convert the primal and dual forms to one with equality constraints (because this is required when talking about basic feasible solutions.)

Suppose we are dealing with a maximization primal.

The inequality constraint $Ax leq b$ can be projected into a higher space by adding slack variables $u$ to get an equality constraint, $$Ax + u = b.$$ Note that $x geq 0, u geq 0$. Thus the actual matrix we're looking at is $[A I]$, of dimension $m times (m + n)$. The rank of this 'primal' matrix is the rank of $A$, so $m$. So, the primal has $m$ basic variables.

The dual of this has the feasible region $A^T y geq c$ where $y geq 0$. However, we need to convert this to an equality constraint too! Add slack variables $s$ to get $$ A^T y - s = c $$ where $y geq 0, s geq 0$.
Note that the matrix we're dealing with in the dual is now $[A^T -I]$, of dimension $n times (m + n)$. This is not the transpose (or the negative of the transpose, even if $-I$ were $I$.) of the 'primal' matrix, because the dimensions don't match! You can see that the rank of this matrix is $n$, because of the rows of the identity matrix. So, the dual has $n$ basic variables.

Thus, if $m neq n$, the dual and primal have a different number of basic variables.

share|cite|improve this answer

edited 2 days ago

answered Apr 7 at 20:22

AmeyaAmeya

113

$endgroup$

add a comment | 

$begingroup$

The confusion here stems from the fact that you must first convert the primal and dual forms to one with equality constraints (because this is required when talking about basic feasible solutions.)

Suppose we are dealing with a maximization primal.

The inequality constraint $Ax leq b$ can be projected into a higher space by adding slack variables $u$ to get an equality constraint, $$Ax + u = b.$$ Note that $x geq 0, u geq 0$. Thus the actual matrix we're looking at is $[A I]$, of dimension $m times (m + n)$. The rank of this 'primal' matrix is the rank of $A$, so $m$. So, the primal has $m$ basic variables.

The dual of this has the feasible region $A^T y geq c$ where $y geq 0$. However, we need to convert this to an equality constraint too! Add slack variables $s$ to get $$ A^T y - s = c $$ where $y geq 0, s geq 0$.
Note that the matrix we're dealing with in the dual is now $[A^T -I]$, of dimension $n times (m + n)$. This is not the transpose (or the negative of the transpose, even if $-I$ were $I$.) of the 'primal' matrix, because the dimensions don't match! You can see that the rank of this matrix is $n$, because of the rows of the identity matrix. So, the dual has $n$ basic variables.

Thus, if $m neq n$, the dual and primal have a different number of basic variables.

share|cite|improve this answer

edited 2 days ago

answered Apr 7 at 20:22

AmeyaAmeya

113

$endgroup$

share|cite|improve this answer

edited 2 days ago

answered Apr 7 at 20:22

AmeyaAmeya

113

answered Apr 7 at 20:22

AmeyaAmeya

113

answered Apr 7 at 20:22

AmeyaAmeya

113