\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{Gram-Schmidt process} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{linear_algebra}{}\paragraph*{{Linear algebra}}\label{linear_algebra} [[!include homotopy - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{GramSchmidtOnHilbertSpaces}{Gram--Schmidt process on Hilbert spaces}\dotfill \pageref*{GramSchmidtOnHilbertSpaces} \linebreak \noindent\hyperlink{ViaGaussianElimination}{Via Gaussian elimination}\dotfill \pageref*{ViaGaussianElimination} \linebreak \noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak \noindent\hyperlink{legendre_polynomials}{Legendre polynomials}\dotfill \pageref*{legendre_polynomials} \linebreak \noindent\hyperlink{CategorifiedGramSchmidtProcess}{Categorified Gram--Schmidt process}\dotfill \pageref*{CategorifiedGramSchmidtProcess} \linebreak \noindent\hyperlink{related_entries}{Related entries}\dotfill \pageref*{related_entries} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{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 [[matrix|matrices]], the Gram--Schmidt process is a procedure of factorization of a invertible matrix $M$ in the [[general linear group]] $GL_n(\mathbb{R})$ (or $GL_n(\mathbb{C})$) as a [[matrix product|product]] $M = U T$ 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 [[vector bundle]] (e.g., the [[tangent bundle]] of a [[Riemannian manifold]] or a [[Kähler manifold]]) from $GL_n$ to the [[orthogonal group]] $O_n$ (or the [[unitary group]] $U_n$). \hypertarget{GramSchmidtOnHilbertSpaces}{}\subsection*{{Gram--Schmidt process on Hilbert spaces}}\label{GramSchmidtOnHilbertSpaces} In this section, ``basis'' is understood to signify an ordered independent set whose [[linear span]] is [[dense subspace|dense]] in a [[Hilbert space]] $H$ seen as a [[metric space]]. We will describe the Gram--Schmidt process as applied to a $d$-dimensional Hilbert space for some [[cardinal]] $d$ with a basis $v_0, v_1, \ldots$ consisting of $d$ vectors. The orthonormal basis $u_0, u_1, \ldots$ produced as output is defined recursively by a) subtracting the orthogonal projection to the closed subspace generated by all previous vectors and b) normalizing. We denote the orthogonal projection onto a closed subspace $A$ by $\pi_A\colon H\to A$ and the normalization $v/\|v\|$ of a vector $v \in H$ by $N(v)$. For [[ordinal]]s $\alpha \lt d$ define \begin{displaymath} u_\alpha \coloneqq N\left(v_\alpha - \pi_{S_\alpha}(v_\alpha)\right) \end{displaymath} where $S_\alpha$ is the closure of the span of $\{v_\beta: \beta \lt \alpha\}$, noting that the projection $\pi_{S_\alpha}$ is known to exist, since $H$ is complete. This can be rewritten more explicitly using transfinite recursion as \begin{displaymath} u_\alpha = N\left(v_\alpha - \sum_{\beta \lt \alpha} \langle v_\alpha, u_\beta\rangle u_\beta\right) \end{displaymath} where the sum on the right is well defined by the Bessel inequality, i.e. only countably many coefficients are non-zero and they are square-summable. A simple (transfinite) inductive argument shows that the $u_\alpha$ are unit vectors orthogonal to each other, and that the span of $\left\{u_\beta \colon \beta \lt \alpha\right\}$ is equal to the span of $\left\{v_\beta \colon \beta \lt \alpha\right\}$ for $\alpha \leq d$. Therefore $u_0, u_1, \ldots$ is an orthonormal basis of $H$. \begin{remark} \label{}\hypertarget{}{} \textbf{(Application to non-bases)} If we apply the Gram--Schmidt process to a well-ordered independent set whose closed linear span $S$ is \emph{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 $\|v\| \neq 0$. However, it does work to [[discrete fields]], such as the algebraic closure of the rationals, as seen in elementary undergraduate linear algebra.) \end{remark} \hypertarget{ViaGaussianElimination}{}\subsection*{{Via Gaussian elimination}}\label{ViaGaussianElimination} There is an alternative algorithm via [[Gaussian elimination]] which for a set of vectors produces an orthogonal basis for its linear span (\hyperlink{PursellTrimble91}{Pursell-Trimble 91}). In the special case that the original vectors are linearly independent and after normalizing the resulting orthogonal basis to an orthonormal basis, the output of this algorithm is an orthonormal basis as produced also by the Gram-Schmidt process. \begin{lemma} \label{LUDecompositionOfPositiveSemidefiniteMatrices}\hypertarget{LUDecompositionOfPositiveSemidefiniteMatrices}{} \textbf{(LU-decomposition of [[positive semidefinite matrices]])} Every [[positive semidefinite matrix]] $M$ has a [[matrix product]]-decomposition \begin{displaymath} M \;=\; L \cdot U \end{displaymath} where \begin{enumerate}% \item $L$ is \begin{enumerate}% \item a [[lower triangular matrix]] \item an [[invertible matrix]] \end{enumerate} \item $U$ is an [[upper triangular matrix]]. \end{enumerate} \end{lemma} (\hyperlink{PursellTrimble91}{Pursell-Trimble 91, p. 4}) \begin{prop} \label{OrthogonalBasisOfLinearSpanByLUDecomposition}\hypertarget{OrthogonalBasisOfLinearSpanByLUDecomposition}{} \textbf{(orthogonal basis of linear span via LU-decomposition)} Let $(a_j)$ be a [[tuple]] of [[vectors]] of the same length, hence let \begin{displaymath} A = (A_{i j}) \coloneqq ((a_j)_i) \end{displaymath} be the [[matrix]] whose $j$th column is $a_j$. Since the [[matrix product]] $M \coloneqq A^T \cdot A$ of $A$ with its [[transpose matrix]] is necessarily a [[positive semidefinite symmetric matrix]] it has an LU-decomposition according to Lemma \ref{LUDecompositionOfPositiveSemidefiniteMatrices}: \begin{displaymath} A^T \cdot A \;=\; L \cdot U \,. \end{displaymath} Then the column vectors $(\hat q_j)$ of the matrix \begin{displaymath} \widehat Q \;\coloneqq\; A \cdot (L^{-1})^T \end{displaymath} constitute an orthogonalization of the original tuple of vectors $(a_i)$ in that the non-zero $\hat q_j$ form an orthogonal [[linear basis]] of the [[linear span]] of the $(a_j)$. \end{prop} (\hyperlink{PursellTrimble91}{Pursell-Trimble 91, top of p. 5}) \begin{remark} \label{}\hypertarget{}{} That the matrix $L$ in Prop. \ref{OrthogonalBasisOfLinearSpanByLUDecomposition} is [[lower triangular matrix|lower triangular]] and [[invertible matrix|invertible]] (by Lemma \ref{LUDecompositionOfPositiveSemidefiniteMatrices}) means that its [[inverse matrix]] $L^{-1}$ is also a [[lower triangular matrix]] which reflects a process of [[row reduction]] from $A^T \cdot A$ to $U$. Accordingly, the orthogonalization in Prop. \ref{OrthogonalBasisOfLinearSpanByLUDecomposition} may be understood as applying [[Gauss elimination]] to \begin{displaymath} \big[A^T \cdot A \vert A^T \big] \;\mapsto\; \big[ \widehat Q^T\big] \end{displaymath} \end{remark} (\hyperlink{PursellTrimble91}{Pursell-Trimble 91, p. 3}) \hypertarget{examples}{}\subsection*{{Examples}}\label{examples} \hypertarget{legendre_polynomials}{}\subsubsection*{{Legendre polynomials}}\label{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])$ of [[square integrable functions]] in the [[closed interval]], equipped with the standard [[inner product]] defined by \begin{displaymath} \langle f, g\rangle = \int_{-1}^1 \widebar{f(x)} g(x) d x \end{displaymath} By the [[Stone-Weierstrass theorem]], the space of [[polynomials]] $\mathbb{C}[x]$ is dense in $H$ according to its standard inclusion, and so the polynomials $1, x, x^2, \ldots$ form an ordered basis of $H$. Applying the Gram--Schmidt process as \hyperlink{GramSchmidtOnHilbertSpaces}{above}, one readily computes the first few orthonormal functions: \begin{displaymath} u_1(x) = N(1) = 1/2 \end{displaymath} \begin{displaymath} u_2(x) = N(x - 0) = \sqrt{3/2} x \end{displaymath} \begin{displaymath} 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) \end{displaymath} 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 \begin{displaymath} \langle P_n, P_m\rangle = \frac{2}{2n + 1}\delta_{m, n} \end{displaymath} where $\delta_{m, n}$ is the [[Kronecker delta]]. \hypertarget{CategorifiedGramSchmidtProcess}{}\subsection*{{Categorified Gram--Schmidt process}}\label{CategorifiedGramSchmidtProcess} Many aspects of the Gram--Schmidt process can be [[categorification|categorified]] so as to apply to [[2-Hilbert spaces]] as indicated at \emph{[[Schur's lemma]]} in the section \emph{\href{Schur's+lemma#InterpretationInCategoricalAlgebra}{In terms of categorical algebra}}; We will illustrate the basic idea with an example that was suggested to us by [[James Dolan]]. (See also at \emph{[[permutation representation]]} the sections \emph{\href{permutation+representation#ExamplesVirtualPermutationRepresentations}{Examples -- Virtual permutation representations}}.) Consider the [[category of representations]] $S_n Rep$ over the [[complex numbers]] of the [[symmetric group]] $G \coloneqq S_n$. (As a running example, we consider $S_4$; up to [[isomorphism]], there are five [[irreducible representations]] \begin{displaymath} U_{(4)}, \, U_{(3 1)}, \, U_{(2 2)}, \, U_{(2 1 1)}, \, U_{(1 1 1 1)} \end{displaymath} 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 \emph{$2$-orthonormal basis} in the sense that any two of them $U_i, U_j$ satisfy the relation \begin{displaymath} hom_G(U_i, U_j) \cong \delta_{i j} \cdot \mathbb{C} \end{displaymath} (where $hom_G$ denotes the [[hom-object|hom vector space]] in $S_n Rep$, and $n \cdot \mathbb{C}$ indicates a [[direct sum]] of $n$ copies of $\mathbb{C}$). 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$, [[conjugation|conjugate]] to one of type $P_{(n_1 \ldots n_k)} = S_{n_1} \times \ldots \times S_{n_k}$ where $n_i$ is the length of the $i^{th}$ row of the Young diagram. The group $S_n$ [[transitive action|acts transitively]] on the [[orbit space]] of [[cosets]] \begin{displaymath} S_n/P_{(n_1 \ldots n_k)} \end{displaymath} and these actions give linear [[permutation representations]] $\mathbb{C}\big[S_n/P_{(n_1 \ldots n_k)}\big]$ of $S_n$. Equivalently, these are [[linear representations]] $V_i$ which are [[induced representation|induced]] from the [[trivial representation]] along inclusions of parabolic subgroups. We claim that \begin{enumerate}% \item these representations form a $\mathbb{Z}$-[[linear basis]] of the [[representation ring]] $R(S_n)$, \item we may calculate their characters using a categorified Gram--Schmidt process. \end{enumerate} We indicate the proof: Given two such [[parabolic subgroups]] $P$, $Q$ in $G = S_n$, the \emph{$2$-inner product} \begin{displaymath} hom_G(\mathbb{C}[G/P], \mathbb{C}[G/Q]) \end{displaymath} may be identified with the [[linear span|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, \ldots, 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 $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): \begin{displaymath} \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) \end{displaymath} To reiterate: this matrix is the [[decategorification]] (a matrix of [[dimensions]]) of a matrix of $2$-inner products where the $(i j)$-entry is of the form \begin{displaymath} hom_G(V_i, V_j) \cong V_i^* \otimes_G V_j \end{displaymath} where the $V_i$ are [[induced representation|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 [[decategorification|decategorified]] form of the 2-matrix with entries \begin{displaymath} hom_G(U_i, V_j) \cong U_i^* \otimes_G V_j \end{displaymath} where $U_i$ is the [[irrep]] corresponding to the $i$ Young diagram (as listed above). The [[upper triangular matrix]] is \begin{displaymath} \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) \end{displaymath} and we read off from the columns the following decompositions into irreducible components: \begin{displaymath} V_1 \cong U_1 \end{displaymath} \begin{displaymath} V_2 \cong U_1 + U_2 \end{displaymath} \begin{displaymath} V_3 \cong U_1 + U_2 + U_3 \end{displaymath} \begin{displaymath} V_4 \cong U_1 + 2 U_2 + U_3 + U_4 \end{displaymath} \begin{displaymath} V_5 \cong U_1 + 3 U_2 + 2 U_3 + 3 U_4 + U_5 \end{displaymath} The last representation $V_5$ is the [[regular representation]] of $S_4$ (because the [[parabolic subgroup]] is [[trivial group|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$: \begin{displaymath} dim(U_1) = 1, \, dim(U_2) = 3, \, dim(U_3) = 2, \, dim(U_4) = 3, \, dim(U_5) = 1 \end{displaymath} (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 \begin{displaymath} \left( \array {1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 1 & -1 & -1 & 1 & 0 \\ -1 & 2 & 1 & -3 & 1 } \right) \end{displaymath} 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$: \begin{displaymath} U_1 \cong V_1 \end{displaymath} \begin{displaymath} U_2 \cong -V_1 + V_2 \end{displaymath} \begin{displaymath} U_3 \cong -V_2 + V_3 \end{displaymath} \begin{displaymath} U_4 \cong V_1 - V_2 - V_3 + V_4 \end{displaymath} \begin{displaymath} U_5 \cong -V_1 + 2V_2 + V_3 - 3 V_4 + V_5 \end{displaymath} 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 $Rep(S_4)$. Analogous statements hold for each symmetric group $S_n$. \hypertarget{related_entries}{}\subsection*{{Related entries}}\label{related_entries} \begin{itemize}% \item [[Hermite normal form]] \item [[Smith normal form]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} See also \begin{itemize}% \item Wikipedia, \emph{\href{https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process}{Gram-Schmidt process}} \end{itemize} The formulation via Gaussian elimination is due to \begin{itemize}% \item Lyle Pursell, S. Y. Trimble, \emph{Gram-Schmidt orthogonalization by Gauss Elimination}, The American Mathematical Monthly Vol. 98, No. 6 (1991), pp. 544-549 (\href{https://www.jstor.org/stable/2324877}{jstor:2324877}) \end{itemize} [[!redirects Gram–Schmidt process]] [[!redirects Gram--Schmidt process]] [[!redirects Gram-Schmidt]] [[!redirects Gram–Schmidt]] [[!redirects Gram--Schmidt]] [[!redirects Gram-Schmidt procedure]] [[!redirects Gram–Schmidt procedure]] [[!redirects Gram--Schmidt procedure]] [[!redirects Gram-Schmidt factorization]] [[!redirects Gram–Schmidt factorization]] [[!redirects Gram--Schmidt factorization]] [[!redirects Gram-Schmidt factorisation]] [[!redirects Gram–Schmidt factorisation]] [[!redirects Gram--Schmidt factorisation]] [[!redirects Gram–Schmidt algorithm]] \end{document}