8

Let us suppose you have $m$ real-valued vectors of length $n$ where $n \geq m$.

How fast can you determine if they are linearly independent?

In the case where $m = n$ one way to determine independence would be to compute the determinant of the matrix whose rows are the vectors. I tried some googling and found that the best known algorithm to compute the determinant of a square matrix with $n$ rows runs in $O \left ( n^{2.373} \right )$. That puts an upper bound on the case where $m = n$. But computing the determinant seems like an overkill. Furthermore it does not solve the case where $n > m$.

Is there a better algorithm? What is the known theoretical lower bound on the complexity of such an algorithm?

Martin Drozdik
  • 812

3 Answers3

4

Forming a matrix $A$, this problem is equivalent to determining whether $Ax = 0$ has nontrivial solutions. Solving a linear system can be decomposed into a series of matrix multiplications, so it will always have the complexity of the fastest matrix multiplication algorithm.

Christopher A. Wong
  • 22,445
  • 3
  • 51
  • 82
  • A series op operations of length bounded independently of the size of the matrix? – Marc van Leeuwen Mar 22 '13 at 09:30
  • 1
    Yes, that is one way to approach the problem. But I do not need the solution of the equation you propose, I just need to know whether or not it has a solution. – Martin Drozdik Mar 22 '13 at 09:37
  • The number of said multiplications only scales as $\log{N}$, where $N$ is the length of the matrix; the general strategy is to solve a series of subproblems formed by dividing the matrix into successive powers of $2$. – Christopher A. Wong Mar 22 '13 at 09:59
  • @MartinDrozdik, I'm not exactly sure what you mean. – Christopher A. Wong Mar 22 '13 at 10:02
  • You provided one solution to the problem. I do not doubt that it is correct. But I am interested in the solution with the smallest known computational complexity. – Martin Drozdik Mar 22 '13 at 16:56
  • 1
    I would be extremely surprised if it were possible to calculate the rank of a matrix faster than one could solve the associated linear system. – Christopher A. Wong Mar 22 '13 at 20:02
1

Like Christopher A. Wong said this comes down to solving $Ax=0$ and checking for a nontrivial solution. There are a few approaches to doing this in the case $n>m$. One way would be to solve by finding the LU decomposition of $A$ and then using forward and backward substitution. This can be accomplished in $O(\frac{2}{3}n^3)$ floating point operations. You could also find the QR decomposition of $A$. Then the rank of $A$ will be the same as the rank of $R$. Since $R$ is triangular it is easy to see it's rank. This can be accomplished in $O(n^3)$ floating point operations. There are many ways to implement the QR decomposition. If you are going to do it I suggest using the Householder transformation approach, it is the most numerically stable. A good place to read about this stuff is Fundamentals of Matrix Computations by Watkins.

Wintermute
  • 3,828
  • Since $O(n^3)$ is worse than $O(m^2n)$, I gather from the reply to my comment under the question that these ideas are not good enough to interest OP. – Marc van Leeuwen Mar 22 '13 at 12:32
0

Please use the following steps

  1. Arrange the vectors in form of a matrix with each vector representing a column of matrix.

  2. Vectors of a matrix are always Linearly Dependent if number of columns is greater than number of rows (where m > n).

  3. Vectors of a matrix having number of rows greater than or equal to number of columns (where n >= m) are Linearly Independent only if Elementry Row Operations on Matrix can convert it into a Matrix containing only Mutually Orthogonal Identitity Vectors (An Identity Vector is a Vector having 1 as one of the component and 0 as other components). Otherwise the vectors are Linearly Dependent

So, the only thing that is required is a fast algorithm to do elementry row operations on a matrix with n>=m to check whether the vectors in it can be converted to Mutually Orthogonal Identitity Vectors

If someone thinks this answer is wrong, please prove it by giving some counter examples of Matrices.

Arup Hore
  • 119