# Multicollinearity and SVD

I compute the Singular Value Decomposition of a $n \times n$ matrix. If the matrix is not full rank, and I have 2 collinear columns, I end up with one singular value equal to 0. Is it possible to find out which columns of the original matrix are collinear from the result of the SVD ?

This is a simple example. I would then like, for a more complicated matrix where a group of columns are multicollinear, to identify this group.

Therefore I want to know if the SVD can go beyond just knowing the number of multicollinear columns and identifying the multicollinear group of columns.

You can do the following:

Compute the SVD of $A\in\mathbb{R}^{n\times n}$: $$A=[U_1,U_2]\begin{bmatrix}\Sigma & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}V_1^T \\ V_2^T\end{bmatrix},$$ where $V_2\in\mathbb{R}^{n\times k}$, $k=\dim\mathcal{N}(A)$, is contains the orthonormal basis of the nullspace of $A$. Next, compute the QR factorization with pivoting of the matrix $V_2^T$ such that $$\tag{✽} V_2^T\Pi=QR=Q\begin{bmatrix}R_1 & R_2\end{bmatrix},$$ where $\Pi$ is a permutation matrix and $R_1$ is nonsingular upper triangular matrix (e.g., MATLAB's qr function with three output arguments can do it). From $AV_2=0$ and (✽), we have now $$0 = AV_2=A\Pi\Pi^TV_2=A\Pi(V_2^T\Pi)^T=A\Pi\begin{bmatrix}R_1^T \\ R_2^T\end{bmatrix}Q^T$$ and hence (since $Q$ is square and non-singular) $$\tag{☺} A\Pi\begin{bmatrix}R_1^T \\ R_2^T\end{bmatrix}=0.$$ Now partition $A\Pi$ as $A\Pi=[A_1,A_2]$ conformingly to the partitioning of $R$ to get from (☺) that $$A_1R_1^T+A_2R_2^T=0,$$ therefore $$A_1=-A_2R_2^TR_1^{-T}.$$ Consequently, the columns of $A_1$ can be written as linear combinations of the columns of $A_2$ (with the coefficients given by the matrix $-R_2^TR_1^{-T}$). Note that you don't need to compute these coefficients, but only to compute the pivoted QR factorization. The permutation matrix can then be directly used to identify these dependent columns.

A simple MATLAB example:

The following matrix $A$ has rank 2:

A =

1     3     1     2
0     0     0     0
1     0     0     0
1     3     1     2


Using

[U S V]=svd(A)


gives

U =

0.7063   -0.0344    0.7071    0.0000
0         0   -0.0000    1.0000
0.0486    0.9988    0.0000    0.0000
0.7063   -0.0344   -0.7071   -0.0000

S =

5.4835         0         0         0
0    0.9650         0         0
0         0    0.0000         0
0         0         0    0.0000

V =

0.2665    0.9638         0         0
0.7728   -0.2136    0.5976    0.0000
0.2576   -0.0712   -0.3586    0.8944
0.5152   -0.1424   -0.7171   -0.4472


Hence

V2 = V(:,3:4)


Compute the QR factorisation of $V_2^T$ with pivoting:

[Q R e]=qr(V2','vector')

Q =

-0.3721    0.9282
0.9282    0.3721

R =

0.9636   -0.1482         0   -0.2224
0   -0.8321         0    0.5547

e =

3     4     1     2


We can see, that the columns 3 and 4 are dependent on the others (actually only the second one from the structure of $R_2$).

• Thank you very much ! That works very well, I am also able to detect quasi-multicollinearity, which was the reason to use SVD in the first place. – vkubicki Apr 23 '14 at 16:37