Gram-Schmidt orthogonalization

The process implemented here in a while loop follows quite closely the process described in the textook in the section about the Gram-Schmidt process.

A step by step example

We start with a list of vectors.

gl = {{1, 1, 1, 1}, {0, 1, 0, -1}, {-1, 1, 0, 0}}

First we need to decide whether the vectors are linearly dependent or not. That is done by RowReduce

RowReduce[gl]

For vectors to be linearly independent we need 1 in each row. That is, no zero rows are allowed. The following function will test that.

Min[Map[Max[#] &, RowReduce[gl]]]

Min[
      Map[Max[#] &, 
        RowReduce[{{1, 1, 1, 1}, {1, 1, 1, -1}, {0, 1, -1, 1}, {0, 0, 
              0, 1}}]]]

The vectors in the above list are linearly dependent.

After we made sure that our list consists of linearly independent vectors, we start Gram-Schmidt process by forming a list of future orthogonal vectors. We start with the first vector which is just the first vector in the given list.

ol = {gl[[1]]};

Now we define the vector to be added, that is the second vector of the list. We call this vector  lv

lv = (gl[[2]] - (gl[[2]] . ol[[1]]/ol[[1]] . ol[[1]]) 
            ol[[1]])

Now we append the normalized  lv  vector to the list ol and at the same time we rename the list

ol = Append[ol, lv]

We repeat this process.

Clear[lv];  
    lv = gl[[3]] - (gl[[3]] . 
                    ol[[1]]/ol[[1]] . 
                    ol[[1]] 
              ol[[1]] + gl[[3]] . 
                    ol[[2]]/ol[[2]] . 
                    ol[[2]] 
              ol[[2]])

ol = Append[ol, lv]

ol

Length[ol]

Length[gl]

The corresponding  While  loop

The above process is ideally made for While loop. Since we are working with exact values it is a good idea to FullSimplify at each step.

Clear[GS, gl, ol, lv]; 

\(GS[gl_] := 
      Module[{ol, lv}, 

 (*\ 
          we\ have\ to\ do\ an\ if\ statement\ since\ the\ given\ list\ of\ vectors\ might\ be\ linearly\ dependent\ and\ in\ that\ case\ Gram - 
            Schmidt\ process\ will\ not\ work\ *) 

If[
Min[
              Map[Max[#] &, RowReduce[gl]]] == 
            0, 

 (*\ 
            the\ previous\ condition\ decides\ if\ the\ vectors\ are\ linearly\ independent\ or\ not; \ so, \ 
            if\ linearly\ dependent\ we\ just\ state\ so\ *) 

"The vectors are linearly dependent!", 

 (*\ 
We\ start\ the\ list\ of\ orthogonal\ vectors\ by\ using\ the\ first\ vector\ in\ gl\ list\ of\ \(\(vectors\)\(.\)\)\ 
*) 

ol = {gl[[1]]}; 

While[
            Length[ol] < Length[gl], 
 (*\ 
              now\ calculate\ the\ vector\ to\ be\ appended, \ 
              call\ it\ lv\ *) 

Clear[
              lv]; \ 

lv = 
              FullSimplify[
                gl[[Length[ol] + 1]] - 
                  Sum[\(gl[[Length[ol] + 
                                1]] . 
                            ol[[
                              k]]\/ol[[
                              k]] . 
                            ol[[k]]\) 
                      ol[[k]], {k, 1, 
                      Length[ol]}]]; 

 (*\ \ now\ we\ append\ the\ vector\ \ lv\ \ to\ the\ list\ ol\ *) 

ol = 
              Append[ol, lv]]; \ 

 (*\ 
            While\ will\ repeat\ the\ above\ procedure\ until\ lengths\ of\ \ ol\ \ and\ gl\ \ are\ the\ same\ *) 

FullSimplify[
            ol]]
]\)

Testing of the command

To test the command we give a list of several vectors and execute the command:

GS[{{1, 1, 1}, {0, 1, 0}, {-1, 1, 0}}]

GS[{{1, 1, 1, 1}, {1, -1, 1, -1}, {0, 1, -1, 
          1}}]

Now test if the vectors obtained by the Gram-Schmidt orthogonalization are in fact orthogonal:

GS[{{1, 1, 1, 1}, {1, -1, 1, -1}, {0, 1, -1, 1}}] . 
      Transpose[
        GS[{{1, 1, 1, 1}, {1, -1, 1, -1}, {0, 1, -1, 
              1}}]]

GS[{{1, 1, 1, 1, 1}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0}}]

GS[{{0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 1}}]

GS[{{1, 1, 1, 1, 1}, {1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}}]

GS[{{1, 1, 1, 1, 1}, {1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 
          2}}]

GS[{{1, 1, 1, 1, 1}, {1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 
          2}, {4, 5, 1, 2, 3}}]

GS[{{1, 1, 1, 1}, {1, 1, 1, -1}, {0, 1, -1, 1}, {0, 0, 0, 
          1}}]

To test our command we need to prouce "large" matrices. I do it by choosing random integers. Below is 6X4 matrix with random integers. I call it rM.

rM =  
      Map[Map[Random[Integer, {-9, 9}] &, Range[1, 7]] &, 
        Range[1, 5]]

GS[rM]

GS[rM] . Transpose[GS[rM]]

Timing[Table[
          GS[Map[Map[Random[Integer, {-9, 9}] &, Range[1, 6]] &, 
              Range[1, 4]]], {k, 1, 200}];]