Testing for linear dependence among the columns of a matrix

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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))

Answer 4

Rank, r of a matrix = number of linearly independent columns (or rows) of a matrix. For a n by n matrix A, rank(A) = n => all columns (or rows) are linearly independent.