All of the solutions to Ax=b

It should be simple right? Well, there are 7 different possible cases, and only 3 have simple solutions. Lets summarize.

Summary

We study

Ax=bAx = b

where ACm×nA \in \mathbb{C}^{m\times n}, xCnx \in \mathbb{C}^n and bCbb \in \mathbb{C}^{b}.

We will also use the adjoint ACn×mA^* \in \mathbb{C}^{n \times m} of AA.

A few useful properties:

  1. If, and only if, bR(A)b \in R(A), there exists a solution xx.
  2. If b∉R(A)b \not \in R(A) we are interested in finding a solution to brb_r which minimises the residual, Axb\|Ax - b\|.
  3. If there are linearly independent columns, AA must be tall, and admits the left inverse A+=(AA)1AA^+ = (A^* A)^{-1}A^*
  4. If there are linearly independent rows, AA must be fat, and admits the right inverse A+=A(AA)1A^+ = A^* (A A^*)^{-1}.
  bR(A)    b \in R(A) \implies solution exists b∉R(A)    b\not \in R(A)\implies solution does not exists
indep. cols: N(A)={0}N(A) = \{0\} (tall) unique: x=A+b=(AA)1Abx = A^+ b = (A^* A)^{-1} A^* b least squares: x~=A+b=(AA)1Ab\tilde x = A^+ b = (A^* A)^{-1} A^* b
indep. rows: N(A)={0}N(A^*) = \{0\} (fat) non-unique: x=xr+xnx = x_r + x_n, and smallest sol: xr=A+b=A(AA)1bx_r = A^+ b = A^* (A A^*)^{-1} b Impossible Case (by rank-nullity)
dep. cols: N(A){0}N(A) \neq \{0\} (tall) solution not unique no solution
dep. rows: N(A){0}N(A^*) \neq \{0\} (fat) (same as above) solution not unique (same as above) no solution

Left and Right Inverses

Following Boyd’s textbook on linear algebra, we define

  1. The left inverse XX of a matrix AA is any martix that satisfies XA=IX A = I.
  2. The right inverse YY of a matrix AA is any matrix that satisfies AY=IA Y = I.

These have the following useful properties (proofs are simple, and I refer you to Boyd’s book, Ch 11):

  1. The left inverse exists iff and only if the columns of AA are linearly independent.
  2. A matrix can only have a left inverse if it is tall (or square).
  3. If a matrix AA has left inverse XX, then a solution to Ax=bAx = b is x=Xbx = X b.
  4. A left invertible matrix AA has left inverse X=(AA)1AX = (A^*A)^{-1}A^*.
  5. Left inverses are, in general, not unique.

Similarly, we can take the transpose of the above claims:

  1. The right inverse exists iff and only if the rows of AA are linearly independent.
  2. A matrix can only have a right inverse if it is fat (or square).
  3. If a matrix AA has right inverse YY, then a solution to Ax=bAx = b is x=Ybx = Y b.
  4. A right invertible matrix AA has right inverse Y=A(AA)1Y = A (AA^*)^{-1}.
  5. Right inverses are, in general, not unique.

Then suppose a matrix is both left and right invertible. Then the left and right inverses are equal and unique!

XA=I, and AY=I    X=X(AY)=(XA)Y=YXA = I, \quad \text{ and } \quad AY = I\\ \implies X = X (AY) = (XA) Y = Y

Thus the inverse of a matrix AA, if it exists, is A1X=YA^{-1} \triangleq X = Y.

Notice that this only makes sense for square matrices, since for the left inverse to exist it must be tall, and for the right inverse to exist it must be fat. Thus, AA must be square.

The two special inverses X=(AA)1AX = (A^*A)^{-1}A^* or Y=A(AA)1Y = A (AA^*)^{-1} require the matrices (AA)(A^*A) or (AA)(AA^*) to be invertible. This is always possible for left/right invertible matrices AA, ie, if they have either linearly independent columns or rows.

But what about if this is not the case? We can use the Moore-Penrose Psuedo-Inverse, which is any matrix A+A^+ that satisfies the following four properties:

  1. AA+A=AAA^+A = A
  2. A+AA+=A+A^+ A A^+ = A^+
  3. (AA+)=AA+(AA^+)^* = AA^+
  4. (A+A)=A+A(A^+A)^* = A^+A

The psuedo inverse always exists, and is always unique. If AA is left or right invertible, the psuedo-inverse is the left or right inverse. If AA is invertible, the psuedo inverse is the inverse of AA. This makes it a powerful abstraction of inverses, but you need to be careful: A+AIA^+ A \neq I in general.

Solutions of simple cases

todo, proofs of each of the three simple cases above.

Solutions of other cases, using Singular Value Decomposition

todo.