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.
Solving Linear Systems with Singular Matrices
1 Answers
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$.
-
0I 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? – 2012-06-25
-
0Perhaps the Schur decomposition would be a better choice if numerics are involved. This would involve power of triangular matrices, however... – 2012-06-25
-
0@042: what do you mean by $x_0'$? Robert Israel's solution works regardless of whether or not the eigenvalues are zero. – 2012-06-25
-
0@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. – 2012-06-25
-
0By the way, in [these notes](http://www.vwl.unibe.ch/studies/3107_e/DifferenceEquations.pdf), 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). – 2012-06-25
-
0In the case of a $d \times d$ Jordan block $J$ for eigenvalue $\lambda = 0$, ${n \choose j} \lambda^{n-j} = 1$ for $j=n$ and $0$ otherwise. This corresponds to solutions with $x_1 = A x_0, x_2 = A^2 x_0, \ldots, x_{d-1} = A^{d-1} x_0$, and $x_n = 0$ for $n \ge d$. – 2012-06-25
-
0@042: I am not familiar with this method. Robert Israel's is different and, as I said, does not depend on the singularity of the matrix. You might want to work out what it says in the $2 \times 2$ case to get a better idea of what's going on. – 2012-06-25
-
0@RobertIsrael Do I understand right, that we use a convention that $0^0 = 1$? If so, then it starts to make sense to me. Is there any reason that we are allowed to use $0^0 = 1$ in this case? Thank you very much anyway! – 2012-06-25
-
0Yes, we use $0^0=1$ here. Why? Because it makes $\lambda^0$ a continuous function of $\lambda$ at $\lambda=0$. – 2012-06-25