How does Gram–Schmidt process produce normalized, orthogonal rows?

Question

Assuming a square matrix, I see how this process would produce orthonormal columns, but I cannot see the rows also turn out to be orthonormal after this process? It seems like some kind of witchery.

edit: to clarify, I don't see how a square matrix whose columns are normalized and pairwise orthogonal, implies that it's rows will also be normalized and pairwise orthogonal

Answer 1

No, after getting then you have to normalize them. Suppose $\vec a, \vec b, \vec c$ are linearly independent non-orthogonal vectors then we can create $\vec u, \vec v, \vec w$ by G-S procedure as $$\vec u= \vec a, ~~\vec v= \vec b+ r \vec u, ~~s.t~~ \vec v. \vec u=0 \implies r=-\frac{\vec a. \vec b}{\vec a. \vec a}$$ Bext lert $\vec w=\vec c+s \vec u+t \vec v ~~s.t~~ \vec w.\vec u=0=\vec w. \vec v.$ We can determine scalars $s$ and $t$, After most (not in between) we can normalize $\vec u, \vec v, \vec w$ to get orthonormal basis as $(\hat u, \hat v, \hat w)$

Answer 2

The Gram-Schmidt process applies to any matrix, even rectangular ones. Even if one neglects cases where the GS vectors are linearly dependent, the rows of a GS matrix in general are not orthogonal. Only when there are $n$ linearly independent vectors does it turn out to be unitary.

For example, orthogonalization of this matrix of columns gives $$\begin{pmatrix}1&1\\2&0\\2&1\end{pmatrix}\mapsto \frac{1}{3}\begin{pmatrix}1&2\\2&-2\\2&1\end{pmatrix}=:A$$ The rows are not orthogonal. Compare with a full matrix: $$\begin{pmatrix}1&1&1\\2&0&2\\2&1&3\end{pmatrix}\mapsto \frac{1}{3}\begin{pmatrix}1&2&-2\\2&-2&-1\\2&1&2\end{pmatrix}=:U$$

Notice how, by definition of GS, $A^TA=I_{2\times2}$. So, what does $A$ do? It maps $\mathbb{R}^2$ into a plane in $\mathbb{R}^3$. And $A^T$? It maps back from $\mathbb{R}^3$ such that the plane becomes $\mathbb{R}^2$ and the plane's normal becomes $0$. (This is because $A^Tn=\begin{pmatrix}a_1\cdot n\\a_2\cdot n\\\vdots\end{pmatrix}=0$.)

In a square non-degenerate matrix, there is no normal left over, so $U^T$ has no null vectors. Again, by construction $U^TU=I$, and $Ue_i=u_i$ are the column vectors, while $U^Tu_i=U^TUe_i=e_i$. Since the $u_i$ span the whole vector space, any vector $v$ can be written as a linear combination of them, so $$UU^Tv=UU^T(\sum_i\alpha_iu_i)=U(\sum_i\alpha_ie_i)=\sum_i\alpha_iu_i=v$$ Hence $UU^T=I$, which states that the rows are orthonormal.

Answer 3

The witchery comes from working in finite-dimensional spaces, where the left inverse of a square matrix is always the same as the right inverse.

Theorem: If $V$ is a finite-dimensional vector space over a field $\mathscr{F}$, and if $A$ is an invertible linear transformation on $V$, then $A^{-1}$ is a polynomial in $A$ and, hence, commutes with $A$. So every left inverse of $A$ is a right inverse and vice-versa.

Proof: Suppose $V$ is an invertible $n\times n$ matrix, and suppose $$ m(\lambda) = \lambda^n+a_{n-1}\lambda^{n-1}+\cdots+a_1\lambda+a_0 $$ is its minimal polynomial. Then $a_0\ne 0$ because that would imply $$ (A^{n-1}+a_{n-1}A^{n-2}+\cdots+a_1I)A=0, $$ and the invertibility of $A$ would imply that $A^{n-1}+a_{n-1}A^{n-2}+\cdots+a_1I=0$, which would contradict the minimality of the polynomial $m$. Therefore, $$ A^{-1}=\frac{1}{a_0}(A^{n-1}+a_{n-1}A^{n-2}+\cdots+a_1I). $$ Hence, a left inverse of $A$ will always be a right inverse because it must commute with $A$. $\;\;\blacksquare$

The inverse of a square orthogonal matrix $U$ is its transpose $U^{\perp}$. Therefore, $$ U^{\perp}U=I \iff UU^{\perp}=I $$ The first equality is equivalent to the columns of $U$ forming an orthonormal basis. The second equality is equivalent to the rows of $U$ forming an orthonormal basis.