Is there an algorithim for determining whether vectors LI?

[merlin2007]

Hi all,

If I have a list of vectors, such as ((1,0,1),(1,-1,1),(3,5,3),(2,3,2)), I know I can find out whether at least three of them are linearly independent by trying all four possible lists of three. For example, I might pick the first three and check whether the third one can be written as a linear combination of the first two. However, I am wondering whether there is a faster way to traverse all four.

Thanks.

 

[galactus]

For your set, any 4 vectors in \(\displaystyle R^{3}\) are linearly dependent.

Here's an example of how to tell if a set is dependent or independent.

Let's determine whether the vectors \(\displaystyle v_{1}=(1,-2,3), \;\ v_{2}=(5,6,-1), \;\ v_{3}=(3,2,1)\)

It is linearly independent if it has only the trivial solution, so:

The vector equation is \(\displaystyle k_{1}v_{1}+k_{2}v_{2}+k_{3}v_{3}=0\)

becomes \(\displaystyle k_{1}(1,-2,3)+k_{2}(5,6,-1)+k_{3}(3,2,1)=(0,0,0)\)

Equate coefficients:

\(\displaystyle \begin{array}{ccc|c}1&5&3&0\\-2&6&2&0\\3&-1&1&0\end{array}\)

Therefore, \(\displaystyle v_{1}, \;\ v_{2}, \;\ v_{3}\) form a dependent set if the system has a nontrivial solution and indpendent if it has only the trivial solution. Solving the system, we get:

\(\displaystyle k_{1}=\frac{-1}{2}t, \;\ k_{2}=\frac{-1}{2}t, \;\ k_{3}=t\)

The system has nontrivial solutions, so it is a dependent set.

You can also check the determinant. If it is 0, then the set is dependent. If it is non-zero, then it is independent.