MATLAB: Determine linear dependency of vectors in (close to) singular matrix

badlyclosedecompositiondependencydependentlinearMATLABmatrixnullprecisionqrrcondscaledsingulartovectorsworking

Is there a way in MATLAB to find which of the vectors in a (close to) singular matrix are linearly dependent or can be represented by a combination of other vectors?

Best Answer

There are two error messages for matrices close to singular:
>> ones(4)\randn(4, 1)
Warning: Matrix is singular to working precision.
>> (ones(4)+randn(4)*eps)\randn(4, 1)
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =
4.163336e-17.
Of course, whether MATLAB recognizes a matrix as singular or just close to singular can also depend on the round-off error when analyzing the input matrix - with numerical computations, there's not much of a difference between a matrix that is close to singular and a singular matrix.
Here is an example of some methods to determine which vectors are linearly dependent. First we'll construct matrix A with the 4th column linearly dependent on the 1st and 2nd column:
>> A = randn(4, 3);
>> A(:, 4) = A(:, [1 2])*randn(2, 1)*10;
>> A\ones(4, 1);
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND =
7.056059e-19.
The NULL function returns a set of vectors x such that A*x is zero (up to round-off error). If the null vector is zero in a component, it means that this column vector is linearly independent of the others.
>> null(A)
ans =
0.9527
-0.2732
0.0000
-0.1333
This shows that columns 1, 2, and 3 are linearly dependent. There's no way of knowing that we constructed the 4th column from the first two.
Another method is based on the QR decomposition of A: If a third output is used, this reorders the columns to move linearly dependent columns to the right.
>> [Q, R, P] = qr(A, 0)
Q =
-0.1991 0.7234 0.2649 -0.6057
-0.5153 0.1696 -0.8400 0.0046
0.7746 0.4829 -0.3769 0.1572
-0.3078 0.4634 0.2866 0.7800
R =
-20.7439 -4.1195 0.1691 -2.8538
0 3.8128 -0.0418 -0.0120
0 0 1.4445 0.4143
0 0 0 0.0000
P =
4 3 2 1
The last row is all zero, and P tells us that this is the first column in matrix A. So we can see that the first column of A is linearly dependent on the other three columns. This could just as well have chosen the 2nd or 4th column, as they are all linearly dependent on each other.
Related Question