Long live Gram-Schmidt algorithmWhat is meant by dependence and independence here is linear dependence and independence.Given a set S of vectors, and a inner product function.
Required to decide: S is an independent set.
I've always thought that deciding whether a set is dependent or not requires computing determinants which is not an easy task, but there is a more reliable method, which is the
Gram-Schmidt algorithm.
The whole idea is that, applying the algorithm on a dependent set will always result in a zero vector in the output set, what is left now is to check if the zero vector exists in the output set.
Example
Suppose we are now in the 2-D Euclidean space (R two), given the set S:
S = { v1=(1,2) , v2=(2,4) }
It is easy to see that S is a dependent set because, (2,4) = 2(1,2).
Applying the Gram-Schmidt algorithm on S:
- u1 = v1 = (1,2)
- u2 = v2 - Proj(u1 , v2)
= (2,4) - < (1,2) , (2,4) > / < (1,2) , (1,2) >
= (2,4) - (10 / 5) x (1,2)
= (2,4) - 2(1,2) = (0,0)
The output set is I = { u1=(1,2) , u2=(0,0) }, which contains a zero vector.
Checking for the zero vector can be done more efficiently.
The expected run-time for the Gram-Schmidt algorithm is cubic, which is the same that of the most efficient determinant algorithm (probably the Gauss Elimination method), but is more reliable and it always works.
Muhammad El-Halaby
Posts
