Singular Matrix

Many linear algebra calculations eventually meet a matrix that cannot be inverted. Matlab prints a warning, the solution of a linear system becomes very large, or an algorithm stops with a division by zero. The cause is usually a singular matrix, or a matrix that is very close to one.

Singular Matrix is defined as a Matrix which does not have matrix inverse. It means

the determinant of Singular Matrix is 0.
for Ax = b, if A is a singular matrix. Ax=b cannot be solved uniquely. It has either no solution or infinitely many solutions.
for Ax = b, if you convert this into simultaneous equation, at least one of the equations is dependent on the others, that is, it is a linear combination of the other equations.

I'll first collect the tests that tell you whether a square matrix is singular, and check them on two small examples. Then we'll see exactly what happens to Ax = b in each of the two cases. The last section deals with matrices that are almost singular, which cause more trouble in practice than exactly singular ones.

How do you recognize a singular matrix ?

The definition says that the inverse does not exist, but it gives no way to check that. In practice, you use one of several equivalent tests. For a square n x n matrix A, they all give the same answer, so you can pick the one that is easiest for the problem at hand.

A is singular exactly when any one of the following holds, and then all of them hold. The determinant is 0. The rank is less than n. The columns are linearly dependent, and so are the rows. There is a nonzero vector x with Ax = 0. At least one eigenvalue is 0. The smallest singular value is 0. Each test describes the same fact in a different way. A maps some nonzero vector to the zero vector, so the information along that vector cannot be recovered.

Let's apply the tests to A = [[1, 2], [2, 4]], where each inner bracket is one row. The determinant is 1 x 4 - 2 x 2 = 0. The second row is 2 times the first, so the rank is 1. The vector x = [2, -1]^T gives Ax = [0, 0]^T. The eigenvalues are 0 and 5, and the singular values are 5 and 0. Every test agrees.

A 3 x 3 example shows why the third bullet above talks about one equation depending on the others, and not about two equal equations. In B = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], no row is a multiple of another row. But row 3 = 2 x row 2 - row 1, because 2 x [4, 5, 6] - [1, 2, 3] = [7, 8, 9]. So the rank is 2, and x = [1, -2, 1]^T gives Bx = 0.

All the tests are equivalent : det(A) = 0, rank(A) < n, dependent columns, a nonzero solution of Ax = 0, a zero eigenvalue and a zero singular value all mean the same thing.
Only square matrices are called singular : a non-square matrix has no inverse in any case. For it, the rank is the useful quantity. See Rank.
Dependence can involve more than two rows : B has no pair of proportional rows and is still singular.
The vector x with Ax = 0 spans the null space : for A = [[1, 2], [2, 4]], every multiple of [2, -1]^T is sent to zero.

What happens to Ax = b when A is singular ?

For an invertible A, the system Ax = b has exactly one solution, x = A^-1b. A singular A removes that guarantee. What remains depends on b. So we cannot say that the system has no solution. We can only say that it has no unique solution.

Take A = [[1, 2], [2, 4]] again. With b = [3, 6]^T, the two equations are x₁ + 2x₂ = 3 and 2x₁ + 4x₂ = 6. The second is 2 times the first, so it adds no information. Every point on the line x₁ + 2x₂ = 3 is a solution, for example [3, 0]^T, [1, 1]^T and [0.6, 1.2]^T. So there are infinitely many solutions.

With b = [3, 5]^T, the second equation becomes 2x₁ + 4x₂ = 5. Divided by 2, it says x₁ + 2x₂ = 2.5, while the first equation says 3. Both cannot hold, so there is no solution at all. In a drawing, the two equations are two lines in the plane. With the first b the lines coincide, and with the second b they are parallel.

The rule behind the two cases is the column space of A. Ax is always a combination of the columns of A. For this A, both columns are multiples of [1, 2]^T. So Ax = b has a solution exactly when b is also a multiple of [1, 2]^T. [3, 6]^T is such a multiple, and [3, 5]^T is not.

b in the column space gives infinitely many solutions : any one solution plus any vector of the null space is again a solution.
b outside the column space gives no solution : the equations contradict each other.
The pseudo-inverse selects one answer : pinv(A) x b gives the solution with the smallest length when solutions exist, [0.6, 1.2]^T in the example. When none exists, it gives the least squares answer.
Matlab A\b is not the same thing : for a singular square A, it warns that the matrix is singular and may return Inf or NaN.

Why is an almost singular matrix a problem ?

An exactly singular matrix is rare in measured or computed data. Rounding makes the determinant slightly nonzero, so the matrix looks invertible. The real question is whether it is close enough to singular to make the answer useless.

Let's change one entry of the example to get C = [[1, 2], [2, 4.001]]. Now det(C) = 0.001, and the inverse exists. But its entries are large: C^-1 = [[4001, -2000], [-2000, 1000]]. With b = [3, 6]^T, the solution is [3, 0]^T. With b = [3, 6.001]^T, a change of 0.001 in one entry, the solution becomes [1, 1]^T. A tiny change in the input moved the answer by more than 2.

The condition number measures this sensitivity. It is the ratio of the largest to the smallest singular value. For C it is about 25008, so a relative error in b can grow by that factor in x. A singular matrix has an infinite condition number. As a rough rule, a condition number of 10^k costs about k of the 16 digits that double precision carries.

The determinant is a poor test for this. Its size depends on the scale of the matrix. The 100 x 100 matrix 0.1 x I has det = 10^-100, but its condition number is 1, and its inverse is simply 10 x I. In the other direction, numpy computes the determinant of B above as about 6.7 x 10^-16 instead of exactly 0.

% Matlab / Octave
C = [1 2; 2 4.001];
det(C)          % 0.001  : looks invertible
cond(C)         % about 2.5e4 : sensitive
rank([1 2; 2 4])   % 1 : singular

# Python / numpy
import numpy as np
C = np.array([[1, 2], [2, 4.001]])
np.linalg.cond(C)          # about 2.5e4
np.linalg.matrix_rank(np.array([[1, 2], [2, 4]]))   # 1

Test with rank or cond, not with det : rank counts the singular values above a tolerance, and cond is a ratio of two singular values. So neither depends on the scale of the matrix.
A large condition number means an unreliable solution : for C, a change of 0.001 in b changed x from [3, 0]^T to [1, 1]^T.
Regularization is the usual cure : adding a small multiple of I, as in (A^TA + λI)x = A^Tb, or dropping the smallest singular values keeps the answer stable. MMSE equalization in a MIMO receiver uses the first of these ideas.
Related pages : see Determinant, Eigen Vector/Value and SVD.