Editing Schur decomposition

{{Short description|Matrix factorisation in mathematics}}
In the [[mathematics|mathematical]] discipline of [[linear algebra]], the '''Schur decomposition''' or '''Schur triangulation''', named after [[Issai Schur]], is a [[matrix decomposition]]. It allows one to write an arbitrary complex square matrix as [[Matrix similarity|unitarily similar]] to an [[Upper-triangular matrix|upper triangular matrix]] whose diagonal elements are the eigenvalues of the original matrix.

== Statement ==
The complex Schur decomposition reads as follows: if {{mvar|A}} is an {{math|''n'' × ''n''}} [[square matrix]] with [[complex numbers|complex]] entries, then ''A'' can be expressed as<ref name=horn1985>{{cite book | last1 = Horn | first1 = R.A. | last2 = Johnson | first2 = C.R. | name-list-style=amp | year=1985 | title = Matrix Analysis | publisher = Cambridge University Press | isbn = 0-521-38632-2}} (Section 2.3 and further at [{{Google books|plainurl=y|id=PlYQN0ypTwEC|page=79|text=Schur}} p. 79])</ref><ref name=Golub1996>{{cite book|last1=Golub | first1= G.H. |last2=Van Loan | first2 = C.F. |name-list-style=amp |year=1996 |title=Matrix Computations | edition=3rd | publisher=Johns Hopkins University Press | isbn=0-8018-5414-8}}(Section 7.7 at [{{Google books|plainurl=y|id=mlOa7wPX6OYC|page=313|text=Schur Decomposition}} p. 313])</ref><ref>{{cite book |first=James R. |last=Schott |title=Matrix Analysis for Statistics |location=New York |publisher=John Wiley & Sons |year=2016 |edition=3rd |isbn=978-1-119-09247-6 |pages=175–178 |url=https://books.google.com/books?id=e-JFDAAAQBAJ&pg=PA177 }}</ref>
<math display="block"> A = Q U Q^{-1}</math>
for some [[unitary matrix]] ''Q'' (so that the inverse ''Q''<sup>−1</sup> is also the [[conjugate transpose]] ''Q''* of ''Q''), and some [[upper triangular matrix]] ''U''. This is called a '''Schur form''' of ''A''. Since ''U'' is [[similar (linear algebra)|similar]] to ''A'', it has the same [[Spectrum of a matrix|spectrum]], and since it is triangular, its [[eigenvalue]]s are the diagonal entries of ''U''.

The Schur decomposition implies that there exists a nested sequence of ''A''-invariant subspaces {{math|1={0} = ''V''<sub>0</sub> ⊂ ''V''<sub>1</sub> ⊂ ⋯ ⊂ ''V<sub>n</sub>'' = '''C'''<sup>''n''</sup>}}, and that there exists an ordered [[orthonormal basis]] (for the standard [[Hermitian form]] of {{math|'''C'''<sup>''n''</sup>}}) such that the first ''i'' basis vectors span {{math|''V''<sub>''i''</sub>}} for each ''i'' occurring in the nested sequence. Phrased somewhat differently, the first part says that a [[linear operator]] ''J'' on a complex finite-dimensional vector space [[Orbit-stabilizer theorem#Orbits and stabilizers|stabilizes]] a complete [[Flag (linear algebra)|flag]] {{math|1=(''V''<sub>1</sub>, ..., ''V<sub>n</sub>'')}}.

There is also a real Schur decomposition. If {{mvar|A}} is an {{math|''n'' × ''n''}} [[square matrix]] with [[real numbers|real]] entries, then ''A'' can be expressed as<ref name=horn1985-2>{{cite book | last1 = Horn | first1 = R.A. | last2 = Johnson | first2 = C.R. | name-list-style=amp | year=1985 | title = Matrix Analysis | publisher = Cambridge University Press | isbn = 0-521-38632-2}} (Section 2.3 and further at [{{Google books|plainurl=y|id=PlYQN0ypTwEC|page=82|text=2.3.4}} p. 82])</ref> <math display="block"> A = Q H Q^{-1}</math> where {{mvar|Q}} is an [[orthogonal matrix]] and {{mvar|H}} is either upper or lower quasi-triangular. A quasi-triangular matrix is a matrix that when expressed as a block matrix of {{math|''2'' × ''2''}} and {{math|''1'' × ''1''}} blocks is triangular. This is a stronger property than being [[Hessenberg matrix|Hessenberg]]. Just as in the complex case, a family of commuting real matrices 
{''A<sub>i</sub>''} may be simultaneously brought to quasi-triangular form by an orthogonal matrix. There exists an orthogonal matrix ''Q'' such that, for every ''A<sub>i</sub>'' in the given family, 
<math display="block"> H_i = Q A_i Q^{-1}</math>
is upper quasi-triangular.

== Proof ==
A constructive proof for the Schur decomposition is as follows: every operator ''A'' on a complex finite-dimensional vector space has an eigenvalue ''&lambda;'', corresponding to some eigenspace ''V<sub>&lambda;</sub>''. Let ''V<sub>&lambda;</sub>''<sup>⊥</sup> be its orthogonal complement. It is clear that, with respect to this orthogonal decomposition, ''A'' has matrix representation (one can pick here any orthonormal bases ''Z''<sub>1</sub> and ''Z''<sub>2</sub> spanning ''V<sub>&lambda;</sub>'' and ''V<sub>&lambda;</sub>''<sup>⊥</sup> respectively)
<math display="block">\begin{bmatrix} Z_1 & Z_2 \end{bmatrix}^{*} A \begin{bmatrix}Z_1 & Z_2\end{bmatrix} = \begin{bmatrix} \lambda \, I_{\lambda} & A_{12} \\ 0 & A_{22} \end{bmatrix}: 
\begin{matrix}
V_{\lambda} \\
\oplus \\
V_{\lambda}^{\perp}
\end{matrix}
\rightarrow
\begin{matrix}
V_{\lambda} \\
\oplus \\
V_{\lambda}^{\perp}
\end{matrix}
</math>
where ''I<sub>&lambda;</sub>'' is the identity operator on ''V<sub>&lambda;</sub>''. The above matrix would be upper-triangular except for the ''A''<sub>22</sub> block. But exactly the same procedure can be applied to the sub-matrix ''A''<sub>22</sub>, viewed as an operator on ''V<sub>&lambda;</sub>''<sup>⊥</sup>, and its submatrices. Continue this way until the resulting matrix is upper triangular. Since each conjugation increases the dimension of the upper-triangular block by at least one, this process takes at most ''n'' steps. Thus the space '''C'''<sup>''n''</sup> will be exhausted and the procedure has yielded the desired result.<ref>{{cite web |last1=Wagner |first1=David |title=Proof of Schur's Theorem |url=https://math.mit.edu/~gs/linearalgebra/ila5/lafe_schur03.pdf |website=Notes on Linear Algebra}}</ref>

The above argument can be slightly restated as follows: let ''&lambda;'' be an eigenvalue of ''A'', corresponding to some eigenspace ''V<sub>&lambda;</sub>''. ''A'' induces an operator ''T'' on the [[quotient space (linear algebra)|quotient space]] '''C'''<sup>''n''</sup>/''V<sub>&lambda;</sub>''. This operator is precisely the ''A''<sub>22</sub> submatrix from above. As before, ''T'' would have an eigenspace, say ''W<sub>&mu;</sub>'' ⊂ '''C'''<sup>''n''</sup> modulo ''V<sub>&lambda;</sub>''. Notice the preimage of ''W<sub>&mu;</sub>'' under the quotient map is an [[invariant subspace]] of ''A'' that contains ''V<sub>&lambda;</sub>''. Continue this way until the resulting quotient space has dimension 0. Then the successive preimages of the eigenspaces found at each step form a flag that ''A'' stabilizes.

== Notes ==
Although every square matrix has a Schur decomposition, in general this decomposition is not unique. For example, the eigenspace ''V<sub>&lambda;</sub>'' can have dimension > 1, in which case any orthonormal basis for ''V<sub>&lambda;</sub>'' would lead to the desired result.

Write the triangular matrix ''U'' as ''U'' = ''D'' + ''N'', where ''D'' is diagonal and ''N'' is strictly upper triangular (and thus a [[nilpotent matrix]]). The diagonal matrix ''D'' contains the eigenvalues of ''A'' in arbitrary order (hence its Frobenius norm, squared, is the sum of the squared moduli of the eigenvalues of ''A'', while 
the Frobenius norm of ''A'', squared, is the sum of the squared [[singular value]]s of ''A''). The nilpotent part ''N'' is generally not unique either, but its [[Matrix norm#Frobenius norm|Frobenius norm]] is uniquely determined by ''A'' (just because the Frobenius norm of A is equal to the Frobenius norm of ''U'' = ''D'' + ''N'').<ref>{{cite web |last1=Higham |first1=Nick |title=What Is a Schur Decomposition? |date=11 May 2022 |url=https://nhigham.com/2022/05/11/what-is-a-schur-decomposition/}}</ref>

It is clear that if ''A'' is a [[normal matrix]], then ''U'' from its Schur decomposition must be a [[diagonal matrix]] and the column vectors of ''Q'' are the [[eigenvector]]s of ''A''. Therefore, the Schur decomposition extends the [[Eigendecomposition of a matrix|spectral decomposition]]. In particular, if ''A'' is [[Positive-definite matrix|positive definite]], the Schur decomposition of ''A'', its spectral decomposition, and its [[singular value decomposition]] coincide.

A [[commutative operation|commuting]] family {''A<sub>i</sub>''} of matrices can be simultaneously triangularized, i.e. there exists a unitary matrix ''Q'' such that, for every ''A<sub>i</sub>'' in the given family, ''Q A<sub>i</sub> Q*'' is upper triangular. This can be readily deduced from the above proof. Take element ''A'' from {''A<sub>i</sub>''} and again consider an eigenspace ''V<sub>A</sub>''. Then ''V<sub>A</sub>'' is invariant under all matrices in {''A<sub>i</sub>''}. Therefore, all matrices in {''A<sub>i</sub>''} must share one common eigenvector in ''V<sub>A</sub>''. Induction then proves the claim. As a corollary, we have that every commuting family of normal matrices can be simultaneously [[Diagonalizable matrix|diagonalized]].

In the infinite dimensional setting, not every [[bounded operator]] on a [[Banach space]] has an invariant subspace. However, the upper-triangularization of an arbitrary square matrix does generalize to [[compact operator]]s. Every [[compact operator]] on a complex Banach space has a [[Flag (linear algebra)#Subspace nest|nest]] of closed invariant subspaces.

== Computation ==
The Schur decomposition of a given matrix is numerically computed by the [[QR algorithm]] or its variants. In other words, the roots of the [[characteristic polynomial]] corresponding to the matrix are not necessarily computed ahead in order to obtain its Schur decomposition. Conversely, the [[QR algorithm]] can be used to compute the roots of any given [[characteristic polynomial]] by finding the Schur decomposition of its [[companion matrix]]. Similarly, the [[QR algorithm]] is used to compute the eigenvalues of any given matrix, which are the diagonal entries of the upper triangular matrix of the Schur decomposition. Although the [[QR algorithm]] is formally an infinite sequence of operations, convergence to machine precision is practically achieved in [[Big O notation|<math>\mathcal{O}(n^3)</math>]] operations.<ref>{{Cite book|last1=Trefethen|first1=Lloyd N.|url=https://www.worldcat.org/oclc/36084666 | title=Numerical linear algebra|last2=Bau|first2=David|date=1997|publisher=Society for Industrial and Applied Mathematics |isbn=0-89871-361-7 |location=Philadelphia|pages=193–194|oclc=36084666}}</ref>
See the Nonsymmetric Eigenproblems section in [[LAPACK]] Users' Guide.<ref>{{cite book| last1=Anderson|first1=E| last2=Bai|first2=Z| last3=Bischof|first3=C| last4=Blackford|first4=S| last5=Demmel|first5=J| last6=Dongarra|first6=J| last7=Du Croz|first7=J| last8=Greenbaum|first8=A| last9=Hammarling|first9=S| last10=McKenny|first10=A| last11=Sorensen|first11=D| title=LAPACK Users guide| date=1995| publisher=Society for Industrial and Applied Mathematics| location=Philadelphia, PA| isbn=0-89871-447-8| url=http://www.netlib.org/lapack/lug/}}</ref>

== Applications ==
[[Lie theory]] applications include:
* Every invertible operator is contained in a [[Borel group]].
* Every operator fixes a point of the [[flag manifold]].

== Generalized Schur decomposition ==
Given square matrices ''A'' and ''B'', the '''generalized Schur decomposition''' factorizes both matrices as <math>A = QSZ^*</math> and <math>B = QTZ^*</math>, where ''Q'' and ''Z'' are [[unitary matrix|unitary]], and ''S'' and ''T'' are [[upper triangular]]. The generalized Schur decomposition is also sometimes called the '''QZ decomposition'''.<ref name=Golub1996/>{{rp|p=375}}
<ref>Daniel Kressner: "Numerical Methods for General and Structured Eigenvalue Problems", Chap-2, Springer, LNCSE-46 (2005).</ref>

The generalized [[eigenvalue]]s <math>\lambda</math> that solve the [[Eigendecomposition of a matrix#Additional topics|generalized eigenvalue problem]] <math>A\mathbf{x}=\lambda B\mathbf{x}</math> (where '''x''' is an unknown nonzero vector) can be calculated as the ratio of the diagonal elements of ''S'' to those of ''T''. That is, using subscripts to denote matrix elements, the ''i''th generalized eigenvalue <math>\lambda_i</math> satisfies <math>\lambda_i = S_{ii} / T_{ii}</math>.

== References ==
<references />

[[Category:Matrix theory]]
[[Category:Articles containing proofs]]
[[Category:Matrix decompositions]]
[[Category:Issai Schur]]