Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?

Question

I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \rangle$ (where $\mathbf u, \mathbf v \in \mathbb R^n$) to:

$u_i v_i$ for the smallest $i \in \{1,2,\dotsc,n\}$ for which $u_i \neq 0$ or $v_i \neq 0$,

then the Gram-Schmidt algorithm changes to Gaussian elimination. Note that that is no longer an inner product! It's even discontinuous, oddly enough. Notice that if we introduce pivoting to Gram-Schmidt, then the pivoted Gram-Schmidt changes to pivoted Gaussian elimination. Notice also that the definition of an orthogonal matrix ($\langle T\mathbf e_i, T\mathbf e_j \rangle = \langle \mathbf e_i, \mathbf e_j \rangle$ for the standard basis $\{e_1,e_2,\dotsc,e_n\}$) changes to a lower triangular matrix whose diagonal entries are $\pm 1$ (followed by column permutation), resulting in the QR decomposition changing to the LR decomposition.

Is there a conceptual reason for this?

Answer 1

I'm not sure how well this will answer the question "why does this happen?" But hopefully will provide more geometric/abstract views of this.

It seems to me that the Gram–Schmidt and Gaussian elimination can both be described as taking a given basis to a special basis. The Gram–Schmidt process produces an orthonormal basis, while Gaussian elimination produces a basis which is standard relative to a fixed flag (with some potential degeneracy problems).

By a flag, I mean a chain of subspaces $V_1\leq V_2 \leq \dotsb \leq V_{n-1} \leq V_n = \mathbb{F}^n$. A basis $v_1,\dotsc v_n$ standard to this flag has the property $\langle v_1,\dotsc, v_k \rangle = V_k$. If our flag is given by $V_k = \langle e_1,\dotsc, e_k \rangle$ where $e_i$ are the basis we are writing our matrices in, then the matrix which has any other standard basis as columns is upper triangular.

Note: by only considering bases we have really focused on the case that our matrices are invertible but these ideas could be extended to the singular case.

By fixing a basis $e_i$ we are also getting a free complementary flag with subspaces $W_{n-k} = \langle e_{k+1},\dotsc, e_n \rangle$ so that $V_k \oplus W_{n-k} = \mathbb{F}^n$ for each $k$. A matrix with columns standard with respect to this flag is lower triangular. I could have started with just this flag but the opposite pair will be useful.

Now we note that the projection step of your altered Gram–Schmidt process is precisely (at step $k+1$) projection along $V_k$ onto $W_{n-k}$ and then normalising (at step $1$, we just normalise). We should be careful here because this only works if our chosen basis $u_1,\dots,u_n$ has the property: $u_k$ projected onto $W_{n-k+1}$ is not in $W_{n-k}$ already (i.e. its component in the $e_k$ is non-zero).

Indeed, your $(u,v)$ could be thought of as exactly the gadget to achieve this without having to follow $k$ around.

Note you can easily adapt this to ensure the number on the diagonal is exactly $1$ and not just $\pm 1$. Obviously, some choices of original basis will cause problems, but otherwise this will take an arbitrary basis to one standard with respect to our second flag.

Correspondingly, it takes an arbitrary matrix (with caveats) into a lower triangular one and we get the LR-decomposition rather than the QR-decomposition.

One more thing to note is that we have found that lower triangular matrix with all $1$'s on the diagonal. In particular this makes it unipotent and indeed the set of all such matrices is the unipotent radical $U^-$ of the group of invertible lower triangular matrices $B^-$. So what we have rediscovered is that $U^-B$ covers a large part of $GL(\mathbb{F}^n)$. Indeed it is a dense subset called the "big cell" of the Bruhat decomposition; see Characterizing the big Bruhat cell of the universal Chevalley groups over $\mathbb C$.

In this Lie group language (focusing on the invertible case), what you have found is a way to move between the Iwasawa decomposition and the Bruhat decomposition (I'm not sure off the top of my head how this would generalise to other semisimple/reductive Lie groups but I think it could).

Answer 2

We begin with the $2 \times 2$ case, where we gain some insight into the general case. We find that we need to invent a new notion to replace quadratic forms in order to generalise these insights to the $n \times n$ case.

Consider the diagonal matrices $D_P = \begin{pmatrix}1 & 0 \\ 0 & 0 \end{pmatrix}$ and $D_S = \begin{pmatrix}1 & 0 \\ 0 & 1 \end{pmatrix}$, where $P$ and $S$ suggestively stand for PLANE and SPHERE. These each determine a quadratic form. A matrix $Q$ is orthogonal with respect to $D_S$ as the quadratic form if $Q$ is orthogonal in the usual sense. So now consider when $Q$ is orthogonal with respect to $D_P$: $$Q D_P Q^T = D_P \implies Q=LP$$ where $L$ is a lower triangular matrix and $P$ is a permutation matrix.

Now notice that the factors in the usual $QR$ decomposition are orthogonal with respect to $D_S$ and $D_P$ respectively. The factors in the $LU$ decomposition are orthogonal with respect to $D_P$ and $\operatorname{adj}(D_P)$ respectively (where we've used the matrix adjugate).

So this suggests what the general case might be:

1. A matrix $M$ can (often?) be written as the product $Q'Q$ where $Q'$ is orthogonal with respect to one quadratic form, and $Q$ is orthogonal with respect to another. There might need to be some additional permutation matrix factors.

2. Column-permuted (or row-permuted) triangularity has something to do with degenerate quadratic forms.

We build on point 2. If we attempt to generalise the above observation to $3 \times 3$ matrices, it doesn't hold, because the theory of degenerate quadratic forms becomes too, errrr, degenerate.

Proposal for an alternative notion to a degenerate quadratic form

We define a Degeneracy-Compensated Quadratic Form on $\mathbb R^n$ to be a sequence of quadratic forms $(Q_1, Q_2, \dotsc)$ where $\forall i, \forall j > i, Q_i(\mathbf v) \neq 0 \implies Q_j(\mathbf v) = 0$. This resembles a chain complex.

Now, a column-permuted upper triangular matrix is a matrix which is orthogonal with respect to the Degeneracy-Compensated Quadratic Form where each $Q_i$ has rank $1$.

We define the corresponding "Hermitian form" by: $$\langle \mathbf u, \mathbf v \rangle = \langle \mathbf u, \mathbf v \rangle_{Q_i},$$ where $i$ is the largest index for which all $j < i$ have $Q_j(\mathbf u) = Q_j(\mathbf v) = 0$.

The obvious generalisation of Gram-Schmidt includes Gaussian Elimination. This suggests that the notion might be a natural one.