Formal evidence for statement involving matrices A and AB times vector x = c

0

$begingroup$

True or false?

If for every $mathbf{c} in F^n$ there is a solution to the system $ABmathbf{x}=mathbf{c}$, then for every c $in F^n$ there is a solution to the system $Bmathbf{x}=mathbf{c}$. I intuitively understand that this is correct, but I am wondering if there is a formal way to prove it.

Thank you!

linear-algebra matrices

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

$endgroup$

add a comment | 

0

$begingroup$

True or false?

If for every $mathbf{c} in F^n$ there is a solution to the system $ABmathbf{x}=mathbf{c}$, then for every c $in F^n$ there is a solution to the system $Bmathbf{x}=mathbf{c}$. I intuitively understand that this is correct, but I am wondering if there is a formal way to prove it.

Thank you!

linear-algebra matrices

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

$endgroup$

add a comment | 

0

0

0

$begingroup$

True or false?

If for every $mathbf{c} in F^n$ there is a solution to the system $ABmathbf{x}=mathbf{c}$, then for every c $in F^n$ there is a solution to the system $Bmathbf{x}=mathbf{c}$. I intuitively understand that this is correct, but I am wondering if there is a formal way to prove it.

Thank you!

linear-algebra matrices

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

$endgroup$

True or false?

If for every $mathbf{c} in F^n$ there is a solution to the system $ABmathbf{x}=mathbf{c}$, then for every c $in F^n$ there is a solution to the system $Bmathbf{x}=mathbf{c}$. I intuitively understand that this is correct, but I am wondering if there is a formal way to prove it.

Thank you!

linear-algebra matrices

linear-algebra matrices

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

share|cite|improve this question

share|cite|improve this question

asked Feb 2 at 14:12

daltadalta

1578

asked Feb 2 at 14:12

daltadalta

1578

asked Feb 2 at 14:12

daltadalta

1578

1578

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

2

$begingroup$

Edit: this solution is only applicable for square matrices. See Sean Lee's counter-example with non-square matrices above.

For a matrix $D$, the existence of a solution to $Dx=c$ for all $cin F^n$ is equivalent to invertibility of $D$ (see this - this is actually only one direction but it is the one we want). In particular, here we get that $AB$ is invertible and by this, $B$ is invertible (and so is $A$).

share|cite|improve this answer

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
  $endgroup$
  – Sean Lee
  Feb 2 at 14:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @SeanLee Right. I missed that. Your solution indeed clears things up, then.
  $endgroup$
  – Yuval Gat
  Feb 2 at 14:27
  

  
  
  
  

add a comment | 

1

$begingroup$

Its not correct.

Take

$$
A = begin{bmatrix}
1 & 0 & 0 \
0 & 1 & 0
end{bmatrix},
B = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix}
$$

Then

$$
AB = begin{bmatrix}
1 & 0 \
0 & 1
end{bmatrix}
$$

Thus there will be a solution for the system $ABbf{x} = bf{c}, forall bf{c} in F^n$ (the solution is just $ bf{x} = bf{c}$), however there will not necessarily be a solution for $B bf{x} = bf{c}$. For example, there is no solution for the following system:
$$
Bbf{x} = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix} bf{x} =
begin{bmatrix}
1 \
0 \
1
end{bmatrix}
$$

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

$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
});


}
});

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

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%2f3097327%2fformal-evidence-for-statement-involving-matrices-a-and-ab-times-vector-x-c%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

2

$begingroup$

Edit: this solution is only applicable for square matrices. See Sean Lee's counter-example with non-square matrices above.

For a matrix $D$, the existence of a solution to $Dx=c$ for all $cin F^n$ is equivalent to invertibility of $D$ (see this - this is actually only one direction but it is the one we want). In particular, here we get that $AB$ is invertible and by this, $B$ is invertible (and so is $A$).

share|cite|improve this answer

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
  $endgroup$
  – Sean Lee
  Feb 2 at 14:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @SeanLee Right. I missed that. Your solution indeed clears things up, then.
  $endgroup$
  – Yuval Gat
  Feb 2 at 14:27
  

  
  
  
  

add a comment | 

2

$begingroup$

Edit: this solution is only applicable for square matrices. See Sean Lee's counter-example with non-square matrices above.

For a matrix $D$, the existence of a solution to $Dx=c$ for all $cin F^n$ is equivalent to invertibility of $D$ (see this - this is actually only one direction but it is the one we want). In particular, here we get that $AB$ is invertible and by this, $B$ is invertible (and so is $A$).

share|cite|improve this answer

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
  $endgroup$
  – Sean Lee
  Feb 2 at 14:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @SeanLee Right. I missed that. Your solution indeed clears things up, then.
  $endgroup$
  – Yuval Gat
  Feb 2 at 14:27
  

  
  
  
  

add a comment | 

2

2

2

$begingroup$

Edit: this solution is only applicable for square matrices. See Sean Lee's counter-example with non-square matrices above.

For a matrix $D$, the existence of a solution to $Dx=c$ for all $cin F^n$ is equivalent to invertibility of $D$ (see this - this is actually only one direction but it is the one we want). In particular, here we get that $AB$ is invertible and by this, $B$ is invertible (and so is $A$).

share|cite|improve this answer

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

$endgroup$

Edit: this solution is only applicable for square matrices. See Sean Lee's counter-example with non-square matrices above.

For a matrix $D$, the existence of a solution to $Dx=c$ for all $cin F^n$ is equivalent to invertibility of $D$ (see this - this is actually only one direction but it is the one we want). In particular, here we get that $AB$ is invertible and by this, $B$ is invertible (and so is $A$).

share|cite|improve this answer

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

share|cite|improve this answer

share|cite|improve this answer

edited Feb 2 at 14:28

edited Feb 2 at 14:28

edited Feb 2 at 14:28

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

answered Feb 2 at 14:22

Yuval GatYuval Gat

9641213

9641213

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
  $endgroup$
  – Sean Lee
  Feb 2 at 14:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @SeanLee Right. I missed that. Your solution indeed clears things up, then.
  $endgroup$
  – Yuval Gat
  Feb 2 at 14:27
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
  $endgroup$
  – Sean Lee
  Feb 2 at 14:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @SeanLee Right. I missed that. Your solution indeed clears things up, then.
  $endgroup$
  – Yuval Gat
  Feb 2 at 14:27
  

  
  
  
  

$begingroup$
This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
$endgroup$
– Sean Lee
Feb 2 at 14:25

$begingroup$
This assumes that $A$ and $B$ are square. There is no such assumption in the question, however.
$endgroup$
– Sean Lee
Feb 2 at 14:25

$begingroup$
@SeanLee Right. I missed that. Your solution indeed clears things up, then.
$endgroup$
– Yuval Gat
Feb 2 at 14:27

$begingroup$
@SeanLee Right. I missed that. Your solution indeed clears things up, then.
$endgroup$
– Yuval Gat
Feb 2 at 14:27

add a comment | 

1

$begingroup$

Its not correct.

Take

$$
A = begin{bmatrix}
1 & 0 & 0 \
0 & 1 & 0
end{bmatrix},
B = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix}
$$

Then

$$
AB = begin{bmatrix}
1 & 0 \
0 & 1
end{bmatrix}
$$

Thus there will be a solution for the system $ABbf{x} = bf{c}, forall bf{c} in F^n$ (the solution is just $ bf{x} = bf{c}$), however there will not necessarily be a solution for $B bf{x} = bf{c}$. For example, there is no solution for the following system:
$$
Bbf{x} = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix} bf{x} =
begin{bmatrix}
1 \
0 \
1
end{bmatrix}
$$

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

$endgroup$

add a comment | 

1

$begingroup$

Its not correct.

Take

$$
A = begin{bmatrix}
1 & 0 & 0 \
0 & 1 & 0
end{bmatrix},
B = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix}
$$

Then

$$
AB = begin{bmatrix}
1 & 0 \
0 & 1
end{bmatrix}
$$

Thus there will be a solution for the system $ABbf{x} = bf{c}, forall bf{c} in F^n$ (the solution is just $ bf{x} = bf{c}$), however there will not necessarily be a solution for $B bf{x} = bf{c}$. For example, there is no solution for the following system:
$$
Bbf{x} = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix} bf{x} =
begin{bmatrix}
1 \
0 \
1
end{bmatrix}
$$

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

$endgroup$

add a comment | 

1

1

1

$begingroup$

Its not correct.

Take

$$
A = begin{bmatrix}
1 & 0 & 0 \
0 & 1 & 0
end{bmatrix},
B = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix}
$$

Then

$$
AB = begin{bmatrix}
1 & 0 \
0 & 1
end{bmatrix}
$$

Thus there will be a solution for the system $ABbf{x} = bf{c}, forall bf{c} in F^n$ (the solution is just $ bf{x} = bf{c}$), however there will not necessarily be a solution for $B bf{x} = bf{c}$. For example, there is no solution for the following system:
$$
Bbf{x} = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix} bf{x} =
begin{bmatrix}
1 \
0 \
1
end{bmatrix}
$$

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

$endgroup$

Its not correct.

Take

$$
A = begin{bmatrix}
1 & 0 & 0 \
0 & 1 & 0
end{bmatrix},
B = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix}
$$

Then

$$
AB = begin{bmatrix}
1 & 0 \
0 & 1
end{bmatrix}
$$

Thus there will be a solution for the system $ABbf{x} = bf{c}, forall bf{c} in F^n$ (the solution is just $ bf{x} = bf{c}$), however there will not necessarily be a solution for $B bf{x} = bf{c}$. For example, there is no solution for the following system:
$$
Bbf{x} = begin{bmatrix}
1 & 0 \
0 & 1 \
0 & 0
end{bmatrix} bf{x} =
begin{bmatrix}
1 \
0 \
1
end{bmatrix}
$$

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

share|cite|improve this answer

share|cite|improve this answer

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

answered Feb 2 at 14:24

Sean LeeSean Lee

828214

828214

add a comment | 

add a comment | 

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

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%2f3097327%2fformal-evidence-for-statement-involving-matrices-a-and-ab-times-vector-x-c%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

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

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

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

Post as a guest

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here