Proof of Triangular Orthonormalization of a Positive Definite Gram Matrix

Throughout, for $x,y\in\mathbb{R}^{d}$ write $\langle x,y\rangle_{G}=x\cdot(Gy)$, combining the dot product with the matrix-vector product; explicitly $\langle x,y\rangle_{G}=\sum_{i,l}x_iG_{il}y_l$, so $\langle\cdot,\cdot\rangle_{G}$ is linear in each argument, and it is symmetric because $G^{\top}=G$ (Transpose of a Real Matrix). For a $d\times d$ matrix $M$, let $\mu_i\in\mathbb{R}^{d}$ denote the vector of entries of the $i$-th row of $M$; expanding the matrix product gives

We repeatedly use the algebra of limits for real sequences (if $a_k\to a$ and $b_k\to b$ in the sense of Limit of a Sequence of Real Numbers, then $a_k+b_k\to a+b$ and $a_kb_k\to ab$, the latter since $|a_kb_k-ab|\le|a_k|\,|b_k-b|+|b|\,|a_k-a|$ with $(a_k)$ bounded), and continuity of the nonnegative square root at positive arguments (for $a\ge0$, $b>0$: $|\sqrt a-\sqrt b|=|a-b|/(\sqrt a+\sqrt b)\le|a-b|/\sqrt b$).

Step 1 (Existence). Let $e_1,\dots,e_d$ be the standard basis vectors. Define recursively

We verify by induction that this is well defined and that for each $i$: the coordinates of $\tau_i$ with index greater than $i$ vanish, the $i$-th coordinate of $\tau_i$ is $\nu_i^{-1/2}>0$, and $\langle\tau_i,\tau_j\rangle_{G}=1$ if $j=i$ and $0$ if $j<i$. For $i=1$: $\nu_1=\langle e_1,e_1\rangle_{G}=G_{11}>0$ by positive definiteness applied to $e_1\ne0$, and the claims are immediate. For the step: by the inductive description, each $\tau_j$ ($j<i$) has vanishing coordinates beyond index $j$, so $w_i$ has $i$-th coordinate $1$ and vanishing coordinates beyond $i$; in particular $w_i\ne0$, hence $\nu_i>0$ by positive definiteness, and $\tau_i$ is defined with the stated coordinate properties. For $j<i$, bilinearity and the inductive orthonormality give

so $\langle\tau_i,\tau_j\rangle_{G}=0$, while $\langle\tau_i,\tau_i\rangle_{G}=\nu_i/\nu_i=1$.

Let $T$ be the matrix whose $i$-th row is $\tau_i$. Then $T$ is lower triangular with diagonal entries $T_{ii}=\nu_i^{-1/2}>0$, and by (1), $(TGT^{\top})_{ij}=\langle\tau_i,\tau_j\rangle_{G}=\delta_{ij}$, i.e., $TGT^{\top}=I_d$.

Step 2 (Triangular inversion, proving claim 2). We first record that $(AB)^{\top}=B^{\top}A^{\top}$ whenever the product is defined, by expanding both sides entrywise from Product of Real Matrices and Transpose of a Real Matrix. Let $M$ be lower triangular with nonzero diagonal entries. For each $j$, forward substitution solves $Mx=e_j$: the equations $\sum_{l\le i}M_{il}x_l=\delta_{ij}$ determine $x_1,\dots,x_d$ successively, and they force $x_l=0$ for $l<j$ and $x_j=1/M_{jj}$. Assembling these solutions as columns yields a lower triangular $S$ with $MS=I_d$ and $S_{jj}=1/M_{jj}$. The matrix $M^{\top}$ is upper triangular with the same nonzero diagonal entries, and the analogous backward substitution yields a matrix $S''$ with $M^{\top}S''=I_d$; transposing this identity gives $S''^{\top}M=I_d^{\top}=I_d$, so $S'=S''^{\top}$ is a left inverse of $M$. Then, by associativity and The Identity Matrix is a Two-Sided Multiplicative Identity,

so $S$ is a two-sided inverse: $M$ is invertible with $M^{-1}=S$ lower triangular, unique by Uniqueness of the Matrix Inverse, with diagonal entries $1/M_{ii}$. Applied to $M=T$ (whose diagonal is positive), this proves claim 2.

Step 3 (Uniqueness). Let $T'$ be lower triangular with positive diagonal and $T'GT'^{\top}=I_d$. Set $R=T'T^{-1}$. A product of lower triangular matrices is lower triangular with diagonal entries the products of the diagonals: in $(AB)_{ij}=\sum_l A_{il}B_{lj}$, nonzero terms need $l\le i$ and $j\le l$, so the sum vanishes for $j>i$ and equals $A_{ii}B_{ii}$ for $j=i$. Hence $R$ is lower triangular with $R_{ii}=T'_{ii}/T_{ii}>0$. Using $RT=T'T^{-1}T=T'$ (associativity, The Identity Matrix is a Two-Sided Multiplicative Identity) and $(AB)^{\top}=B^{\top}A^{\top}$:

We show a lower triangular $R$ with positive diagonal and $RR^{\top}=I_d$ equals $I_d$, by induction on the row index. Row $1$: $1=(RR^{\top})_{11}=\sum_l R_{1l}^{2}=R_{11}^{2}$, so $R_{11}=1$ (positivity). Assume rows $1,\dots,i-1$ of $R$ coincide with those of $I_d$. For $j<i$: $0=(RR^{\top})_{ij}=\sum_l R_{il}R_{jl}=R_{ij}$, since row $j$ has a single nonzero entry $1$ in position $j$. Then $1=(RR^{\top})_{ii}=\sum_{l\le i}R_{il}^{2}=R_{ii}^{2}$ gives $R_{ii}=1$. Hence $R=I_d$ and $T'=RT=T$.

Step 4 (Stability). First, eventual positive definiteness. Suppose, for contradiction, that for infinitely many $k$ the matrix $G^{(k)}$ is not positive definite; since it is positive semidefinite, for each such $k$ there is $c^{(k)}\ne0$ with $c^{(k)}\cdot(G^{(k)}c^{(k)})=0$, and after dividing by the Euclidean norm $|c^{(k)}|=\sqrt{c^{(k)}\cdot c^{(k)}}>0$ (the quadratic form still vanishes, by bilinearity) we may assume $|c^{(k)}|=1$. Each coordinate sequence is bounded by $1$, so $d$ successive applications of the Bolzano-Weierstrass theorem produce a subsequence along which $c^{(k)}\to c^{*}$ coordinatewise. By the algebra of limits, $c^{*}\cdot c^{*}=\lim|c^{(k)}|^{2}=1$, so $c^{*}\ne0$, and

(finite sums of products of convergent sequences, using $G^{(k)}_{il}\to G_{il}$), contradicting positive definiteness of $G$. Hence there is $K$ with $G^{(k)}$ positive definite for all $k\ge K$.

For $k\ge K$, claim 1 applies to $G^{(k)}$; by the uniqueness just proved, $T^{(k)}$ is exactly the matrix produced by the recursion of Step 1 for $G^{(k)}$, with quantities $w^{(k)}_i,\nu^{(k)}_i,\tau^{(k)}_i$. We prove by strong induction on $i$ that $\tau^{(k)}_i\to\tau_i$ coordinatewise and $\nu^{(k)}_i\to\nu_i$. If $x^{(k)}\to x$ and $y^{(k)}\to y$ coordinatewise, then $\langle x^{(k)},y^{(k)}\rangle_{G^{(k)}}\to\langle x,y\rangle_{G}$, again by the algebra of limits applied to the finite sum $\sum_{i,l}x^{(k)}_iG^{(k)}_{il}y^{(k)}_l$. For $i=1$: $\nu^{(k)}_1=G^{(k)}_{11}\to G_{11}=\nu_1>0$, and by continuity of the square root at $\nu_1>0$, $\tau^{(k)}_1=(\nu^{(k)}_1)^{-1/2}e_1\to\tau_1$ (for large $k$, $\nu^{(k)}_1>0$). For the step: by the inductive hypothesis and the displayed continuity, $\langle e_i,\tau^{(k)}_j\rangle_{G^{(k)}}\to\langle e_i,\tau_j\rangle_{G}$ for each $j<i$, so $w^{(k)}_i\to w_i$ coordinatewise, hence $\nu^{(k)}_i\to\nu_i>0$ and $\tau^{(k)}_i=(\nu^{(k)}_i)^{-1/2}w^{(k)}_i\to\nu_i^{-1/2}w_i=\tau_i$. Since the rows of $T^{(k)}$ are the $\tau^{(k)}_i$, this gives $T^{(k)}\to T$ entrywise. $\square$