Find a condition that b must satisfy so that Ax=b has solution

I'm new to Mathematica, so I'm sorry if this is really simple.

I am trying to find the condition that vector b must satisfy so that Ax=b has solution. I would like to learn a general method, but I'll show my particular case.

Given
$A=\left( \begin{array}{cccccc} -1 & 1 & -1 & 0 & 0 & 0 \\ 1 & 0 & 0 & -1 & -1 & 0 \\ 0 & -1 & 0 & 0 & 1 & -1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ \end{array} \right)$ and $b=\left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \\ b_4 \\ \end{array} \right)$

When performing RowReduction by hand, I end up with matrix $U$ such that the last line is of 0: $$\left( \begin{array}{cccccc} -1 & 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & -1 & -1 & -1 & 0 \\ 0 & 0 & -1 & -1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$

and vector $b$: $$\left( \begin{array}{c} b_1 \\ b_1+b_2 \\ b_1+b_2+b_3 \\ b_1+b_2+b_3+b_4 \\ \end{array} \right)$$

This means that if $b_1+b_2+b_3+b_4=0, Ax=b$ has solution. Otherwise, it does not.

What I've tried (without success)

1. Decompose $A$ into $LU$ so that I can do $L.b$ so as to perform same elemental operations to $b$. LUDecomposition command gives error because $A$ is singular.
2. Tried to find which elemental matrices were used to RowReduce[] $A$. However, I could not find a command that would give said output (my aim was to construct a matrix $Q$ with those numbers such that $Q.A=U$ and then do $Q.b$ to obtain the correct $b$).
3. Tried to augment matrix $A$ such that $$(A|b)= \left( \begin{array}{ccccccc} -1 & 1 & -1 & 0 & 0 & 0 & b_1 \\ 1 & 0 & 0 & -1 & -1 & 0 & b_2 \\ 0 & -1 & 0 & 0 & 1 & -1 & b_3 \\ 0 & 0 & 1 & 1 & 0 & 1 & b_4 \\ \end{array} \right)$$ in order to perform RowReduction and extract $b$. However, the output was not what I expected: RowReduce[(A|b)] outputs $$\left( \begin{array}{ccccccc} 1 & 0 & 0 & -1 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)$$

Again, sorry if this seems too basic, but I spent a lot of time trying to find something here (and on other sites) to no avail. It is very likely that I'm just not looking in the right places, so if you could point me in the right direction, I would be grateful.

Thanks!

• I'm not the expert here, so maybe this is not the right place. But yes, I'm looking for a way to do this in Mathematica. I want to get an output that says that the condition is b1+b2+b3+b4=0. I am not looking for a solution for a given b, so I'm not sure LinearSolve would work in this case (sorry for multiple edits. I kept pressing enter accidentally). – Peanut14 May 15 '16 at 2:28
• LinearSolve[Transpose[mat].mat, Transpose[mat].{b1, b2, b3, b4}] yields something you might want to inspect thoroughly. – J. M. will be back soon May 15 '16 at 2:39
• J. M.: Is that assuming I name A as mat and declare b1=b1 and so on....? As I said, I'm a novice and doing a simple mat=A and running the code you suggested yields an exact copy of the code. What am I doing wrong? – Peanut14 May 15 '16 at 2:44
• Never mind. My mistake. I did mat= (matrix) //MatrixForm, which probably caused the problem. I now see an output. Will inspect it and come back with news! THANKS! – Peanut14 May 15 '16 at 2:46
• I tried studying the output of your suggestion but couldn't make much sense of it. It's very likely that I'm just not looking it the right way. Anyway, seeing as Rashid suggested another way, I won't ask you to bother explaining me :). Many thanks for the help, though! – Peanut14 May 15 '16 at 14:03

You can use Reduce[] to find a set of all conditions as follows:

A = {{-1, 1, -1, 0, 0, 0}, {1, 0, 0, -1, -1, 0}, {0, -1, 0, 0, 1, -1}, {0, 0, 1, 1, 0, 1}};
b = {b1, b2, b3, b4};
x = {x1, x2, x3, x4, x5, x6}
allConditions=Reduce[A.x == b, x]


This returns b1 == -b2 - b3 - b4 && x3 == b2 + b3 + b4 - x1 + x2 && x5 == -b2 + x1 - x4 && x6 == -b2 - b3 + x1 - x2 - x4

Then you can simplify this to the conditions on b with Eliminate[]:

bConditions = Eliminate[allConditions, x]


This returns -b2 - b3 - b4 == b1

Alternatively, you can go straight to Eliminate like this:

Eliminate[A.x == b, x]


This also returns -b2 - b3 - b4 == b1

In either case, we are setting up a system of equations by saying that A.x == b. (Writing {x1,y2}=={x2,y2} is equivalent to saying x1==x2 && y1==y2) Then, we're asking Mathematica to rearrange this system of equations to eliminate the x variables to leave us with conditions on b.

• Thank you Rashid, this seems to have done the trick. I also tested it in another 4x5 matrix (adjusting the code you gave slightly) and it also worked out great. Would explaining how this works be out of scope for this question? – Peanut14 May 15 '16 at 14:01
• @Peanut14, thanks for the comment. I just added a brief explanation as well as a more concise method using Eliminate directly. – Rashid May 15 '16 at 15:47
• That is great! Thanks for the added explanations. – Peanut14 May 17 '16 at 13:10

The way I remember it from my Linear Algebra class is like this:

Clear[b];
A = {{-1, 1, -1, 0, 0, 0}, {1, 0, 0, -1, -1, 0}, {0, -1, 0, 0, 1, -1}, {0, 0, 1, 1, 0, 1}};
bb = Array[b, Length@A];

(*  {b[1] + b[2] + b[3] + b[4] == 0}  *)


That is, the condition for a solution to A.x == b to exist is that b be in the column space of A, which is equivalent to b being orthogonal to the orthogonal complement of the column space of A. A basis for the orthogonal complement is given by NullSpace@Transpose@A, and b is orthogonal to the complement if its matrix/dot product with each basis vector is zero.

The code above works whatever the dimensions and rank of A happen to be. Another example:

v1 = {1, 0, 1, -1, -1, 0};
v2 = {0, 0, 1, 1, 0, 1};
A = {v1, v2, v1 + v2, v1 - v2, v1 + 2 v2};
bb = Array[b, Length@A];

(*  {-b[1] - 2 b[2] + b[5] == 0, -b[1] + b[2] + b[4] == 0, -b[1] - b[2] + b[3] == 0}  *)


Comparison with Eliminate

The numerical NullSpace method is much faster than Eliminate, which proceeds symbolically. In addition NullSpace seems to do a better job with numerical issues, if the data are machine reals.

It's 29 times as fast on the OP's example:

bb = Array[b, First@Dimensions@A];
xx = Array[x, Last@Dimensions@A];

{Eliminate[A.xx == bb, xx]} /. And -> List // Flatten // Length // RepeatedTiming
Thread[NullSpace@Transpose@A.bb == 0] // Length // RepeatedTiming
First@%%/First@%
(*
{0.0016, 1}
{0.0000548, 1}
29.
*)


It's over 3000 times as fast on a machine real 80 x 100 system of rank 75. Further, Eliminate issues a warning (in this specific case) that the system is ill-conditioned. Perhaps as a result, it misses one condition.

SeedRandom[1];
A = RandomReal[1, {80, 75}].RandomReal[1, {75, 100}];
bb = Array[b, First@Dimensions@A];
xx = Array[x, Last@Dimensions@A];

{Eliminate[A.xx == bb, xx]} /. And -> List // Flatten // Length // RepeatedTiming
Thread[NullSpace@Transpose@A.bb == 0] // Length // RepeatedTiming
First@%% / First@%


RowReduce::luc: Result for RowReduce of badly conditioned matrix {{16.3835,15.264,16.5837,16.0416,<<43>>,13.8285,17.0251,15.0488,<<131>>},<<49>>,<<30>>} may contain significant numerical errors. >>

(*
{5.00, 4}
{0.0016, 5}
3.1*10^3
*)


If we change RandomReal to RandomInteger, Eliminate, of course, works perfectly, and it is only 500 times as slow as Nullspace (6.911 sec. vs. 0.013 sec.). Part of the relative slow-down in NullSpace is probably due to the integers generated (up to 2^108) exceeding the maximum machine integer.

• +1 for the linear algebra tutorial. Can you check your last paragraph to make sure it's saying what you intend? You mention earlier that NullSpace is much faster than Eliminate, but in the last sentence you are describing a reason for the slow-down in NullSpace, which is a bit confusing. – bobthechemist May 16 '16 at 15:40
• got it, so Eliminate is speeding up when it is applied to integers rather than reals; however, it is still much slower than NullSpace even under these conditions. – bobthechemist May 16 '16 at 16:32
• Thanks for the detailed explanation Michael E2. I'm currently in my Linear Algebra 1 course and have not seen orthogonal complements of the spaces of a Matrix, so I really only understand the surface of what you are saying. I'll keep this method in mind for when I need to do computations for bigger/weirder matrices. I'll be sure to return to this once I have studied algebra a bit more so I can fully understand what you said :). Would you point me to a place to do reading on the syntax? I had never seen the @ syntax you used. Thanks again! – Peanut14 May 17 '16 at 13:09
• @Peanut14 You're welcome. See this answer for a compilation of funny signs. Use your browser search to find what you're looking for. The @ is not so easy to find in Mathematica's docs, but the link to it is given in the answer. (Simple lin. alg. case: Given a line through $(0,0,0)$, the ⟂ complement of the line is the set of vectors in the plane through the origin ⟂ to the line; and vice versa, the ⟂ complement of the plane is the line. At least you see how learning LA can be useful. :-) – Michael E2 May 17 '16 at 13:43

Solution is so simple if we use mathematics. In Mathematics we know Ax=b has a solution if and only if A and [A,b] have a same Rank. Then it is enough to check Ranks of these matrices by MatrixRankfunction. for b={1,2,3,4} try this code (In general this problem has no solution)

A = {{-1,1,-1,0,0,0},{1,0,0,-1,-1,0},{0,-1,0,0,1,-1},{0,0,1,1,0,1}};
b = {1,2,3,4};
Ab = Insert[Transpose[A],b,7] // Transpose
MatrixRank[A]
MatrixRank[Ab]