Why doesn't Gram-Schmidt work for all matrices?

Question

So I'm doing a MATLAB assignment where the objective is to write code to do the Gram Schmidt algorithm.

I just want to say, my code is almost certainly not the issue, as the same issue arises in other codes.

We're meant to do a GS algorithm, then check that we've done it correctly, given our inputted matrix V, by checking Z = transpose(W)*W is the identity matrix.

However, when I let V be a 3x3 matrix, and have the 9 terms be consecutive values. I.e. first row: 1,2,3, second row: 4,5,6, third row: 7,8,9 etc. The GS algorithm doesn't work? It works if the same values are used but not consecutive, it works if anyone of the values is changed. It works if it's descending not ascending. But it doesn't work if the values are 1,2,...,9 or 2,3,...,10.

Am I wrong? Is the GS algorithm valid for all matrices? Or is this an exception? And if so, why?

Answer 1

The GS algorithm requires that you start with linearly independent vectors. For an $n\times n$ matrix that means the rows should be linearly independent.

Answer 2

It’s not that the Gram-Schmidt algorithm fails or is somehow invalid. The problem is that you’ve given it an invalid input: the G-S algorithm is, strictly speaking, only defined for a linearly-independent set of vectors (the columns of the input matrix). The test you’ve been told to use assumes this as well.

At each iteration, G-S computes the orthogonal projection of the current vector $v_i$ onto the span of the previously-processed vectors, then subtracts that from $v_i$ to finds its component orthogonal to that subspace. What happens if $v_i$ is an element of that subspace? Well, the projection of $v_i$ is $v_i$ itself, so you end up with a zero vector. I’m a bit surprised that you aren’t seeing some sort of divide-by-zero warning or exception when your code tries to normalize that zero vector.

You have a few choices for what to do about this. One is to use only valid inputs—full-rank matrices. Another is to have your implementation throw an error if it ever generates a zero. Another is to discard the zero and keep going. The output matrix might no longer be square. Finally, you can keep the zero, but then you have to come up with some other way to test the correctness of your code.

Incidentally, checking that $W^TW=I$ is a somewhat inadequate test of the output. It does verify that the output is an orthonormal set of vectors, but it does nothing to verify that the spans of the input and output are the same. If the inputs are only ever full-rank square matrices, then that follows from the orthogonality of the output, but not in general.