Mixing
Farkas' lemma proof explanation
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
I have been studying the proof of the following variant of Farkas' Lemma:
A system of linear equations $A mathbfx = mathbfb$ in $d$ variables has a solution iff for all $mathbflambda in mathbbR^d, lambda^T A = mathbf0^T$ implies $lambda^T mathbfb = 0$.
For the direction $Rightarrow$ the proof is easy: Suppose that $Amathbfx = mathbfb$ has a solution $barmathbfx$. Then $lambda^T A = mathbf0^T Rightarrow lambda^TAbarmathbfx=lambda^Tmathbfb=0$
For the other direction the proof that the notes give proceeds as follows:
The implication $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0$ means that both matrices $A in mathbbR^ntimes d$ and $(A|mathbfb) in mathbbR^ntimes (d+1)$ have the same linear dependencies among their rows, therefore the same row rank, which means that they have the same column rank. That means that $mathbfb$ is a linear combination of the columns of $A$ which implies that $Amathbfx = mathbfb$ has a solution.
What I am missing in the second part of the proof is how the starting claim means that both matrices have the same linear dependencies among their rows. Can anyone give an intuitive explanation?
linear-algebra matrix-rank
asked Jul 25 at 13:19
dimkou
535
add a comment |Â
up vote
5
down vote
favorite
I have been studying the proof of the following variant of Farkas' Lemma:
A system of linear equations $A mathbfx = mathbfb$ in $d$ variables has a solution iff for all $mathbflambda in mathbbR^d, lambda^T A = mathbf0^T$ implies $lambda^T mathbfb = 0$.
For the direction $Rightarrow$ the proof is easy: Suppose that $Amathbfx = mathbfb$ has a solution $barmathbfx$. Then $lambda^T A = mathbf0^T Rightarrow lambda^TAbarmathbfx=lambda^Tmathbfb=0$
For the other direction the proof that the notes give proceeds as follows:
The implication $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0$ means that both matrices $A in mathbbR^ntimes d$ and $(A|mathbfb) in mathbbR^ntimes (d+1)$ have the same linear dependencies among their rows, therefore the same row rank, which means that they have the same column rank. That means that $mathbfb$ is a linear combination of the columns of $A$ which implies that $Amathbfx = mathbfb$ has a solution.
What I am missing in the second part of the proof is how the starting claim means that both matrices have the same linear dependencies among their rows. Can anyone give an intuitive explanation?
linear-algebra matrix-rank
asked Jul 25 at 13:19
dimkou
535
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I have been studying the proof of the following variant of Farkas' Lemma:
A system of linear equations $A mathbfx = mathbfb$ in $d$ variables has a solution iff for all $mathbflambda in mathbbR^d, lambda^T A = mathbf0^T$ implies $lambda^T mathbfb = 0$.
For the direction $Rightarrow$ the proof is easy: Suppose that $Amathbfx = mathbfb$ has a solution $barmathbfx$. Then $lambda^T A = mathbf0^T Rightarrow lambda^TAbarmathbfx=lambda^Tmathbfb=0$
For the other direction the proof that the notes give proceeds as follows:
The implication $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0$ means that both matrices $A in mathbbR^ntimes d$ and $(A|mathbfb) in mathbbR^ntimes (d+1)$ have the same linear dependencies among their rows, therefore the same row rank, which means that they have the same column rank. That means that $mathbfb$ is a linear combination of the columns of $A$ which implies that $Amathbfx = mathbfb$ has a solution.
What I am missing in the second part of the proof is how the starting claim means that both matrices have the same linear dependencies among their rows. Can anyone give an intuitive explanation?
linear-algebra matrix-rank
asked Jul 25 at 13:19
dimkou
535
I have been studying the proof of the following variant of Farkas' Lemma:
A system of linear equations $A mathbfx = mathbfb$ in $d$ variables has a solution iff for all $mathbflambda in mathbbR^d, lambda^T A = mathbf0^T$ implies $lambda^T mathbfb = 0$.
For the direction $Rightarrow$ the proof is easy: Suppose that $Amathbfx = mathbfb$ has a solution $barmathbfx$. Then $lambda^T A = mathbf0^T Rightarrow lambda^TAbarmathbfx=lambda^Tmathbfb=0$
For the other direction the proof that the notes give proceeds as follows:
The implication $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0$ means that both matrices $A in mathbbR^ntimes d$ and $(A|mathbfb) in mathbbR^ntimes (d+1)$ have the same linear dependencies among their rows, therefore the same row rank, which means that they have the same column rank. That means that $mathbfb$ is a linear combination of the columns of $A$ which implies that $Amathbfx = mathbfb$ has a solution.
What I am missing in the second part of the proof is how the starting claim means that both matrices have the same linear dependencies among their rows. Can anyone give an intuitive explanation?
linear-algebra matrix-rank
asked Jul 25 at 13:19
dimkou
535
asked Jul 25 at 13:19
dimkou
535
asked Jul 25 at 13:19
dimkou
535
asked Jul 25 at 13:19
dimkou
535
535
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
The equation $lambda^TA= mathbf0^T$ is a statement that a certain linear combination of the rows of $A$ is $0$. Let the rows of $A$ be $A_1,A_2,dots,A_n,$ and suppose that $lambda_1A_1+dots+lambda_nA_n=mathbf0^T$ Then if $lambda^T=(lambda_1,dots,lambda_n)$ we have $lambda^TA= mathbf0^T.$
Under the hypothesis that $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0, (A|mathbfb)$ will have the same linear dependencies as $A$.
answered Jul 25 at 13:42
saulspatz
10.4k21323
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
The equation $lambda^TA= mathbf0^T$ is a statement that a certain linear combination of the rows of $A$ is $0$. Let the rows of $A$ be $A_1,A_2,dots,A_n,$ and suppose that $lambda_1A_1+dots+lambda_nA_n=mathbf0^T$ Then if $lambda^T=(lambda_1,dots,lambda_n)$ we have $lambda^TA= mathbf0^T.$
Under the hypothesis that $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0, (A|mathbfb)$ will have the same linear dependencies as $A$.
answered Jul 25 at 13:42
saulspatz
10.4k21323
add a comment |Â
up vote
6
down vote
accepted
The equation $lambda^TA= mathbf0^T$ is a statement that a certain linear combination of the rows of $A$ is $0$. Let the rows of $A$ be $A_1,A_2,dots,A_n,$ and suppose that $lambda_1A_1+dots+lambda_nA_n=mathbf0^T$ Then if $lambda^T=(lambda_1,dots,lambda_n)$ we have $lambda^TA= mathbf0^T.$
Under the hypothesis that $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0, (A|mathbfb)$ will have the same linear dependencies as $A$.
answered Jul 25 at 13:42
saulspatz
10.4k21323
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
The equation $lambda^TA= mathbf0^T$ is a statement that a certain linear combination of the rows of $A$ is $0$. Let the rows of $A$ be $A_1,A_2,dots,A_n,$ and suppose that $lambda_1A_1+dots+lambda_nA_n=mathbf0^T$ Then if $lambda^T=(lambda_1,dots,lambda_n)$ we have $lambda^TA= mathbf0^T.$
Under the hypothesis that $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0, (A|mathbfb)$ will have the same linear dependencies as $A$.
answered Jul 25 at 13:42
saulspatz
10.4k21323
The equation $lambda^TA= mathbf0^T$ is a statement that a certain linear combination of the rows of $A$ is $0$. Let the rows of $A$ be $A_1,A_2,dots,A_n,$ and suppose that $lambda_1A_1+dots+lambda_nA_n=mathbf0^T$ Then if $lambda^T=(lambda_1,dots,lambda_n)$ we have $lambda^TA= mathbf0^T.$
Under the hypothesis that $lambda^TA= mathbf0^T Rightarrow lambda^Tmathbfb=0, (A|mathbfb)$ will have the same linear dependencies as $A$.
answered Jul 25 at 13:42
saulspatz
10.4k21323
answered Jul 25 at 13:42
saulspatz
10.4k21323
answered Jul 25 at 13:42
saulspatz
10.4k21323
answered Jul 25 at 13:42
saulspatz
10.4k21323
10.4k21323
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862402%2ffarkas-lemma-proof-explanation%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password