# Testing for linear dependence among the columns of a matrix

I have a correlation matrix of security returns whose determinant is zero. (This is a bit surprising since the sample correlation matrix and the corresponding covariance matrix should theoretically be positive definite.)

My hypothesis is that at least one security is linearly dependent on other securities. Is there a function in R that sequentially tests each column a matrix for linear dependence?

For example, one approach would be to build up a correlation matrix one security at a time and calculate the determinant at each step. When the determinant = 0 then stop as you have identified the security who is a linear combination of other securities.

Any other techniques to identify linear dependence in such a matrix are appreciated.

-
Your matrix is positive semi-definite, it's not positive definite though, for it is singular. –  ttnphns Oct 1 '11 at 17:53
What are the dimensions (no. variables; no. samples)? –  Karl Oct 1 '11 at 17:59
Number of columns = 480. # of rows for each time series = 502. In general you find that the larger the time series the sample covariance matrix tends to be positive definite. However, there are many cases where you'd like to use a substantially smaller value of T (or exponentially weight) to reflect recent market conditions. –  Quant Guy Oct 1 '11 at 19:24
The question is ill-posed. If your data matrix is 480 by 502 then saying that the matrix has rank $q < 480$ (the column space of the matrix has dimension $q < 480$) is mathematically equivalent to saying that some column is a linear combination of the others, but you can't pick out one column and say that this is the column that is linearly dependent. So there is no procedure for doing this, and the suggested procedure will pick a quite arbitrary security depending on the order they are included. –  NRH Oct 1 '11 at 21:34
The covariance matrix is symmetric. It is generated by transpose(A) * A. The matrix A has dimensions 480x502. However the covariance matrix is 480x480 –  Quant Guy Oct 1 '11 at 23:26

You seem to ask a really provoking question: how to detect, given a singular correlation (or covariance, or sum-of-squares-and-cross-product) matrix, which column is linearly dependent on which. I tentatively suppose that sweep operation could help. Here is my probe in SPSS (not R) to illustrate.

Let's generate some data:

        v1        v2        v3         v4          v5
-1.64454    .35119   -.06384    -1.05188     .25192
-1.78520   -.21598   1.20315      .40267    1.14790
1.36357   -.96107   -.46651      .92889   -1.38072
-.31455   -.74937   1.17505     1.27623   -1.04640
-.31795    .85860    .10061      .00145     .39644
-.97010    .19129   2.43890     -.83642    -.13250
-.66439    .29267   1.20405      .90068   -1.78066
.87025   -.89018   -.99386    -1.80001     .42768
-1.96219   -.27535    .58754      .34556     .12587
-1.03638   -.24645   -.11083      .07013    -.84446


Let's create some linear dependancy between V2, V4 and V5:

compute V4 = .4*V2+1.2*V5.
execute.


So, we modified our column V4.

matrix.
get X. /*take the data*/
compute M = sscp(X). /*SSCP matrix, X'X; it is singular*/
print rank(M). /*with rank 5-1=4, because there's 1 group of interdependent columns*/
loop i= 1 to 5. /*Start iterative sweep operation on M from column 1 to column 5*/
-compute M = sweep(M,i).
-print M. /*That's printout we want to trace*/
end loop.
end matrix.


The printouts of M in 5 iterations:

M
.06660028    -.12645565    -.54275426    -.19692972    -.12195621
.12645565    3.20350385    -.08946808    2.84946215    1.30671718
.54275426    -.08946808    7.38023317   -3.51467361   -2.89907198
.19692972    2.84946215   -3.51467361   13.88671851   10.62244471
.12195621    1.30671718   -2.89907198   10.62244471    8.41646486

M
.07159201     .03947417    -.54628594    -.08444957    -.07037464
.03947417     .31215820    -.02792819     .88948298     .40790248
.54628594     .02792819    7.37773449   -3.43509328   -2.86257773
.08444957    -.88948298   -3.43509328   11.35217042    9.46014202
.07037464    -.40790248   -2.86257773    9.46014202    7.88345168

M
.112041875    .041542117    .074045215   -.338801789   -.282334825
.041542117    .312263922    .003785470    .876479537    .397066281
.074045215    .003785470    .135542964   -.465602725   -.388002270
.338801789   -.876479537    .465602725   9.752781632   8.127318027
.282334825   -.397066281    .388002270   8.127318027   6.772765022

M
.1238115070   .0110941027   .0902197842   .0347389906   .0000000000
.0110941027   .3910328733  -.0380581058  -.0898696977  -.3333333333
.0902197842  -.0380581058   .1577710733   .0477405054   .0000000000
.0347389906  -.0898696977   .0477405054   .1025348498   .8333333333
.0000000000   .3333333333   .0000000000  -.8333333333   .0000000000

M
.1238115070   .0110941027   .0902197842   .0347389906   .0000000000
.0110941027   .3910328733  -.0380581058  -.0898696977   .0000000000
.0902197842  -.0380581058   .1577710733   .0477405054   .0000000000
.0347389906  -.0898696977   .0477405054   .1025348498   .0000000000
.0000000000   .0000000000   .0000000000   .0000000000   .0000000000


Notice that eventually column 5 got full of zeros. This means (as I understand it) that V5 is linearly tied with some of preceeding columns. Which columns? Look at iteration where column 5 is last not full of zeroes - iteration 4. We see there that V5 is tied with V2 and V4 with coefficients -.3333 and .8333: V5 = -.3333*V2+.8333*V4, which corresponds to what we've done with the data: V4 = .4*V2+1.2*V5.

That's how we knew which column is linearly tied with which other. I didn't check how helpful is the above approach in more general case with many groups of interdependancies in the data. In the above example it appeared helpful, though.

-
Isn't this the reduced row echelon form? If so, aren't there packages / functions available in R? –  Arun Oct 14 '11 at 0:39
@Arun, I'm not R user so can't know. –  ttnphns Oct 14 '11 at 6:42

What I'd try to do here for diagnostic purposes is to take the $502\times 480$ matrix (that is, the transpose) and determine the singular values of the matrix (for diagnostic purposes, you don't need the full singular value decomposition... yet). Once you have the 480 singular values, check how many of those are "small" (a usual criterion is that a singular value is "small" if it is less than the largest singular value times the machine precision). If there are any "small" singular values, then yes, you have linear dependence.

-

Here's a straightforward approach: compute the rank of the matrix that results from removing each of the columns. The columns which, when removed, result in the highest rank are the linearly dependent ones (since removing those does not decrease rank, while removing a linearly independent column does).

In R:

rankifremoved <- sapply(1:ncol(your.matrix), function (x) qr(your.matrix[,-x])\$rank)
which(rankifremoved == max(rankifremoved))

-