nLab
Gram-Schmidt process

Idea

The Gram–Schmidt process is an algorithm which takes as input an ordered basis? of an inner product space and produces as output an ordered orthonormal basis?.

In terms of matrices?, the Gram–Schmidt process is a procedure of factorization of a invertible matrix $M$ in the general linear group ${\mathrm{GL}}_n(ℝ)$ (or ${\mathrm{GL}}_n(ℂ)$) as a product $M=UT$ where $T$ is an upper triangular matrix and $U$ is an orthonormal (or unitary) matrix; as such it is a special case of the more general Iwasawa decomposition? for a (connected) semisimple Lie group. Since the factorization depends smoothly on the parameters, the Gram–Schmidt procedure enables the reduction of the structure group of an inner product bundle (e.g., the tangent bundle of a Riemannian manifold or a Kähler manifold) from ${\mathrm{GL}}_n$ to orthogonal group $O_n$ (or the unitary group $U_n$).

Gram–Schmidt process on Hilbert spaces

In this section, “basis” is understood to signify an ordered independent set whose linear span is dense in a Hilbert space $H$ seen as a metric space. We will describe the Gram–Schmidt process as applied to a countable basis $v_1,v_2,\dots$ of an infinite-dimensional separable Hilbert space, although it would apply just as well to a well-ordered basis of any Hilbert space, separable or not.

The orthonormal basis $u_1,u_2,\dots$ produced as output is defined recursively as follows. We denote the normalization $v/\parallel v\parallel$ of a vector $v\in H$ by $N(v)$. Put

$$u_n=N(v_n-\sum _{k<n}⟨v_n,u_k⟩u_k)$$u_n = N(v_n - \sum_{k \lt n} \langle v_n, u_k\rangle u_k)

where the sum on the right is understood to be empty (equal to $0$) in the case $n=1$. A simple inductive argument shows that the $u_i$ are unit vectors orthogonal to each other, and that the span of $u_1,\dots ,u_n$ is equal to the span of $v_1,\dots ,v_n$. Therefore $u_1,u_2,\dots$ is an orthonormal basis of $H$.

Example of Legendre polynomials

A classic illustration of Gram–Schmidt is the production of the Legendre polynomials.

Let $H$ be the Hilbert space $H=L^2([-1,1])$, equipped with the standard inner product defined by

$$⟨f,g⟩={\int }_{-1}^1\overline{f(x)}g(x)dx$$\langle f, g\rangle = \int_{-1}^1 \bar{f(x)} g(x) d x

By the Stone-Weierstrass theorem, the space of polynomials $ℂ[x]$ is dense in $H$ according to its standard inclusion, and so the polynomials $1,x,x^2,\dots$ form an ordered basis of $H$.

Applying the Gram–Schmidt process, one readily computes the first few orthonormal functions:

$$u_1(x)=N(1)=1/2$$u_1(x) = N(1) = 1/2

$$u_2(x)=N(x-0)=\sqrt{3/2}x$$u_2(x) = N(x - 0) = \sqrt{3/2} x

$$u_3(x)=N(x^2-⟨x^2,1/2⟩1/2-0)=N(x^2-1/3)=3\sqrt{5/2}/2(x^2-1/3)$$u_3(x) = N(x^2 - \langle x^2, 1/2\rangle 1/2 - 0) = N(x^2 - 1/3) = 3\sqrt{5/2}/2(x^2 - 1/3)

The classical Legendre polynomials $P_n(x)$ are scalar multiplies of the functions $u_n$, adjusted so that $P_n(1)=1$; they satisfy the orthogonality relations

$$⟨P_n,P_m⟩=\frac{2}{2n+1}{\delta }_{m,n}$$\langle P_n, P_m\rangle = \frac{2}{2n + 1}\delta_{m, n}

where ${\delta }_{m,n}$ is the Kronecker delta?.

Application to non-bases

If we apply the Gram–Schmidt process to a well-ordered independent set whose closed linear span $S$ is not all of $H$, we still get an orthonormal basis of the subspace $S$. If we apply the Gram–Schmidt process to a dependent set, then we will eventually run into a vector $v$ whose norm is zero, so we will not be able to take $N(v)$. In that case, however, we can simply remove $v$ from the set and continue; then we will still get an orthonormal basis of the closed linear span. (This conclusion is not generally valid in constructive mathematics, since it relies on excluded middle applied to the statement that $\parallel v\parallel \ne 0$. However, it does work to discrete fields, such as the algebraic closure of the rationals, as seen in elementary undergraduate linear algebra.)

Categorified Gram–Schmidt process

Many aspects of the Gram–Schmidt process can be categorified so as to apply to 2-Hilbert spaces. We will illustrate the basic idea with an example that was suggested to us by James Dolan.

Consider the category of complex representations of the symmetric group $S_n$. (As a running example, we consider $S_4$; up to isomorphism, there are five irreducible representations

$$U_{(4)},U_{(31)},U_{(22)},U_{(211)},U_{(1111)}$$U_{(4)}, \, U_{(3 1)}, \, U_{(2 2)}, \, U_{(2 1 1)}, \, U_{(1 1 1 1)}

classified by the five Young diagrams of size 4. To save space, we denote these as $U_1$, $U_2$, $U_3$, $U_4$, $U_5$.) The irreducible representations $U_i$ of $S_n$ form a $2$-orthonormal basis in the sense that any two of them $U_i,U_j$ satisfy the relation

$$\mathrm{hom}(U_i,U_j)\cong {\delta }_{ij}\cdot ℂ$$hom(U_i, U_j) \cong \delta_{i j} \cdot \mathbb{C}

(where $n\cdot ℂ$ indicates a direct sum of $n$ copies of $ℂ$). In fact, the irreducible representations are uniquely determined up to isomorphism by these relations.

There is however another way of associating representations to partitions or Young diagrams. Namely, consider the subgroup of permutations which take each row of a Young diagram or Young tableau of size $n$ to itself; this forms a parabolic subgroup? of $S_n$, conjugate to one of type $P_{(n_1\dots n_k)}=S_{n_1}\times \dots \times S_{n_k}$ where $n_i$ is the length of the $i^{\mathrm{th}}$ row of the Young diagram. The group $S_n$ acts transitively on the orbit space of cosets

$$S_n/P_{(n_1\dots n_k)}$$S_n/P_{(n_1 \ldots n_k)}

and these actions give permutation representations of $S_n$. Equivalently, these are representations $V_i$ which are induced from the trivial representation along inclusions of parabolic subgroups. We claim that these representations form a $\mathbb{Z}$-basis of the representation ring, and we may calculate their characters using a categorified Gram–Schmidt process.

Given two such parabolic subgroups $P$, $Q$ in $G=S_n$, the $2$-inner product

$${\mathrm{hom}}_G(ℂ[G/P],ℂ[G/Q])$$hom_G(\mathbb{C}[G/P], \mathbb{C}[G/Q])

may be identified with the free vector space on the set of double cosets $P\backslash G/Q$. One may count the number of double cosets by hand in a simple case like $G=S_4$. That is, for the 5 representations $V_1,\dots ,V_5$ induced from the 5 parabolic subgroups $P_i$ corresponding to the 5 Young diagrams listed above, the dimensions of the 2-inner products $\mathrm{hom}(V_i,V_j)$ are the sizes of the corresponding double coset spaces $P_i\backslash S_4/P_j$. These numbers form a matrix as follows (following the order of the $5$ partitions listed above):

$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 2& 2& 3& 4\\ 1& 2& 3& 4& 6\\ 1& 3& 4& 7& 12\\ 1& 4& 6& 12& 24\end{array}\right)$$\left( \array {1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 6 \\ 1 & 3 & 4 & 7 & 12 \\ 1 & 4 & 6 & 12 & 24 }\right)

To reiterate: this matrix is the decategorification (a matrix of dimensions) of a matrix of $2$-inner products where the $(ij)$-entry is of the form

$${\mathrm{hom}}_G(V_i,V_j)\cong V_i^{*}{\otimes }_G{V}_j$$hom_G(V_i, V_j) \cong V_i^* \otimes_G V_j

where the $V_i$ are induced from inclusions of parabolic subgroups. The $V_i$ are $\mathbb{N}$-linear combinations of irreducible representations $U_i$ which form a $2$-orthonormal basis, and we may perform a series of elementary row operations which convert this matrix into an upper triangular matrix, and which will turn out to be the decategorified form of the 2-matrix with entries

$${\mathrm{hom}}_G(U_i,V_j)\cong U_i^{*}{\otimes }_G{V}_j$$hom_G(U_i, V_j) \cong U_i^* \otimes_G V_j

where $U_i$ is the irreducible corresponding to the $i$^th Young diagram (as listed above). The upper triangular matrix is

$$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 0& 1& 1& 2& 3\\ 0& 0& 1& 1& 2\\ 0& 0& 0& 1& 3\\ 0& 0& 0& 0& 1\end{array}\right)$$\left( \array {1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 2 & 3 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 1} \right)

and we read off from the columns the following decompositions into irreducible components:

$$V_1\cong U_1$$V_1 \cong U_1

$$V_2\cong U_1+U_2$$V_2 \cong U_1 + U_2

$$V_3\cong U_1+U_2+U_3$$V_3 \cong U_1 + U_2 + U_3

$$V_4\cong U_1+2U_2+U_3+U_4$$V_4 \cong U_1 + 2 U_2 + U_3 + U_4

$$V_5\cong U_1+3U_2+2U_3+3U_4+U_5$$V_5 \cong U_1 + 3 U_2 + 2 U_3 + 3 U_4 + U_5

The last representation $V_5$ is the regular representation of $S_4$ (because the parabolic subgroup is trivial). Since we know from general theory that the multiplicity of the irreducible $U_i$ in the regular representation is its dimension, we get as a by-product the dimensions of the $U_i$ from the expression for $V_5$:

$$\dim (U_1)=1,\dim (U_2)=3,\dim (U_3)=2,\dim (U_4)=3,\dim (U_5)=1$$dim(U_1) = 1, \, dim(U_2) = 3, \, dim(U_3) = 2, \, dim(U_4) = 3, \, dim(U_5) = 1

(the first of the $U_i$ is the trivial representation, and the last $U_5$ is the alternating representation).

The row operations themselves can be assembled as the lower triangular matrix

$$\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ -1& 1& 0& 0& 0\\ 0& -1& 1& 0& 0\\ 1& -1& -1& 1& 0\\ 2& -1& -2& 0& 1\end{array}\right)$$\left( \array{1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 1 & -1 & -1 & 1 & 0 \\ 2 & -1 & -2 & 0 & 1 } \right)

and from the rows we read off the irreducible representations as “virtual” (i.e., $\mathbb{Z}$-linear) combinations of the parabolically induced representations $V_i$:

$$U_1\cong V_1$$U_1 \cong V_1

$$U_2\cong -V_1+V_2$$U_2 \cong -V_1 + V_2

$$U_3\cong -V_2+V_3$$U_3 \cong -V_2 + V_3

$$U_4\cong V_1-V_2-V_3+V_4$$U_4 \cong V_1 - V_2 - V_3 + V_4

$$U_5\cong 2V_1-V_2-2V_3+V_5$$U_5 \cong 2 V_1 - V_2 - 2 V_3 + V_5

which can be considered the result of the categorified Gram–Schmidt process.

It follows from these representations that the $V_i$ form a $\mathbb{Z}$-linear basis of the representation ring $\mathrm{Rep}(S_4)$. Analogous statements hold for each symmetric group $S_n$.