# Solving Linear Systems with Singular Matrices

Good morning! For (say, homogenous) linear systems of the form $$x_{n+1} = A x_n,$$ where $A$ is a nonsingular matrix, each initial value problem can be solved by the method of finding a general solution by means of eigenvalues of $A$. However, for singular matrices, this method need not to be successful for all initial value problems (because of zero eigenvalues) and I was unable to find references for such case. So my question is, is there any general method of solving such systems for singular matrices? Thank you in advance.

-

The trouble with your method is not when $A$ is singular, it's when $A$ is not diagonalizable. The solution of the initial value problem $x_{n+1} = A x_n$, $x_0$ given, is $x_n = A^n x_0$. Now we can write $A = S^{-1} J S$ where $S$ is invertible and $J$ is in Jordan canonical form, and so $x_n = S^{-1} J^n S x_0$. For a $d \times d$ Jordan block $$J = \pmatrix{\lambda & 1 & 0 & \ldots & 0 & 0\cr 0 & \lambda & 1 & \ldots & 0 & 0\cr \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \cr 0 & 0 & 0 & \ldots & \lambda & 1\cr 0 & 0 & 0 & \ldots & 0 & \lambda\cr}$$ $$J^n = \pmatrix{ \lambda^n & {n \choose 1} \lambda^{n-1} & {n \choose 2} \lambda^{n-2} & \ldots & {n \choose {d-2}} \lambda^{n-d+2} & {n \choose {d-1}} \lambda^{n-d+1}\cr 0 & \lambda^n & {n \choose 1} \lambda^{n-1} & \ldots & {n \choose {d-3}} \lambda^{n-d+3} & {n \choose {d-2}} \lambda^{n-d+2}\cr & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \cr 0 & 0 & 0 & \ldots & \lambda^n & {n \choose 1} \lambda^{n-1}\cr 0 & 0 & 0 & \ldots & 0 & \lambda^n\cr}$$ where ${n \choose j} \lambda^{n-j} = 0$ when $n < j$.
I am afraid I don't understand your answer completely. As to my knowledge, if the matrix is not diagonalizable, the matrix must have repeated eigenvalues. But in the case these repeated eigenvalues are not 0, the problem can be solved by taking functions $\lambda^n x_0$ and $n \lambda^n x_0 + \lambda^n x'_0$ to the general solution (similarly for higher multiplicities of $\lambda$). Therefore the only problem is for $\lambda = 0$, which may occur only if the matrix is singular. Am I true? It is not clear to me if your method can be helpful in this case... Could you please be more specific? – 042 Jun 25 '12 at 5:52
@042: what do you mean by $x_0'$? Robert Israel's solution works regardless of whether or not the eigenvalues are zero. – Qiaochu Yuan Jun 25 '12 at 6:51
@QiaochuYuan By $x'_0$ I mean some vector that can be computed if needed as a vector which satisfies $(A - \lambda I) x'_0 = \lambda x_0$. But here it can be viewed just as some unspecified vector. The method I have sketched is to my knowledge the standard method of dealing with repeated eigenvalues, but there is always an assumption, that a matrix is nonsingular, since $n 0^n x_0$ and $0^n x'_0$ aren't linearly independent. So I wanted to ask, if there is a way the method can be applied to singular matrices. I don't understand Robert Israel's solution very well. – 042 Jun 25 '12 at 7:03
By the way, in these notes, page 57, it is stated that it can be assumed without the loss of generality, that a matrix is nonsingular because singularity implies existence of redundant variables. But it is not clear to me what about the case if the initial conditions are not the same for two linearly dependent variables. In fact, the solution may differ for some values of $n$ (I think that just for finitely many $n$, but I am not sure). – 042 Jun 25 '12 at 7:08