# Birkhoff factorization

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Birkhoff_factorization
> Markdown URL: https://mediated.wiki/source/Birkhoff_factorization.md
> Source: https://en.wikipedia.org/wiki/Birkhoff_factorization
> Source revision: 1356841756
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Matrix decomposition in mathematics}}
In mathematics, '''Birkhoff factorization''' or '''Birkhoff decomposition''', introduced by {{harvs|txt|last=Birkhoff|first=George David|authorlink=George David Birkhoff|year=1909}}, is a generalization of the [LU decomposition](/source/LU_decomposition) (i.e. Gauss elimination) to loop groups. 

The factorization of an [invertible matrix](/source/invertible_matrix) <math>M\in\mathrm{GL}_n(\mathbb{C}[z,z^{-1}])</math> with coefficients that are [Laurent polynomials](/source/Laurent_polynomials) in <math>z</math> is given by a product <math>M=M^{+}M^{0}M^{-}</math>, where <math>M^{+}</math> has entries that are polynomials in <math>z</math>, <math>M^{0}=\mathrm{diag}(z^{k_1}, z^{k_2},...,z^{k_n})</math> is diagonal with <math>k_i\in\mathbb{Z}</math> for <math>1\leq i\leq n</math> and <math>k_1\geq k_2\geq ...\geq k_n</math>, and <math>M^{-}</math> has entries that are polynomials in <math>z^{-1}</math>. For a generic matrix we have <math>M^{0}=\mathrm{id}</math>.

Birkhoff factorization implies the [Birkhoff–Grothendieck theorem](/source/Birkhoff%E2%80%93Grothendieck_theorem) of {{harvtxt|Grothendieck|1957}} that [vector bundle](/source/vector_bundle)s over the [projective line](/source/projective_line) are sums of [line bundle](/source/line_bundle)s.

There are several variations where the general [linear group](/source/linear_group) is replaced by some other reductive algebraic group, due to {{harvs|txt|last=Grothendieck | first=Alexander | author-link=Alexander Grothendieck|year=1957}}.
Birkhoff factorization follows from the [Bruhat decomposition](/source/Bruhat_decomposition) for affine Kac–Moody groups (or [loop group](/source/loop_group)s), and conversely the Bruhat decomposition for the affine [general linear group](/source/general_linear_group) follows from Birkhoff factorization together with the Bruhat decomposition for the ordinary general linear group.

== Algorithm ==

There is an effective algorithm to compute the Birkhoff factorization. The following will be based on the book by Clancey-Gohberg,<ref name=clancey-gohberg>{{harvp|Clancey|Gohberg|1981|loc=Theorem 2.1}}.</ref> where a more general case can also be found.

Note that, by the [cofactor matrix](/source/cofactor_matrix) formula, a matrix <math>M</math> being invertible is equivalent to the [determinant](/source/determinant) <math>\operatorname{det} M</math> being a unit in the base ring. In our case this means that <math>\operatorname{det} M = c\cdot z^d</math> for some <math>c \in \mathbb C, d \in \mathbb Z</math>, as these are the only invertible elements in the ring of Laurent polynomials <math>\mathbb C [z, z^{-1}]</math>, and <math>\operatorname{det} M^+</math> and <math>\operatorname{det} M^-</math> are just nonzero constants in <math>\mathbb C</math>, because these are the only units in <math>\mathbb C [z]</math> or  <math>\mathbb C [z^{-1}]</math>. This means that <math>\operatorname{det} M^0 = z^d</math> and, in particular, <math>d = k_1 + \cdots k_n</math>. This will help us determine when the algorithm is finished.

''First step:'' Replace <math>M</math> by <math>z^mM</math> to cancel any denominators, i.e. so that <math>z^mM</math> is defined over <math>\mathbb{C}[z]</math>. Let <math>d = \operatorname{ord}_z \operatorname{det} z^mM</math> be the exponent at <math>z</math>, note that this is now nonnegative.

''Second step:'' Permute the rows and factor out the highest possible power of <math>z</math> in each row, while staying over <math>\mathbb{C}[z]</math>. The permutation has to ensure that the highest powers of <math>z</math> are decreasing. Denote <math>P, D</math> the [permutation matrix](/source/permutation_matrix), and the [diagonal matrix](/source/diagonal_matrix) of the powers, respectively.

<math>M' = D^{-1}\cdot P\cdot M </math>

''Third step:'' If the sum of the powers from step 2 equals <math>d</math>, we are done. Otherwise, perform [row operations](/source/row_operations) without pivoting such that at least one row becomes zero modulo <math>z</math>. Put the factored powers back into our matrix and return to step 2.

By disallowing pivoting, we are asking that the matrix <math>E \in \mathrm{GL}_n(\mathbb C)</math> encoding the row operations is lower triangular.

The matrix to be returned to step 2 is:

<math>M'' = D \cdot E \cdot M'</math>

Note that as long as the determinant of the matrix is not constant, the determinant is zero modulo <math>z</math>, hence the rows are linearly dependent modulo <math>z</math>. Therefore, this step can be carried out.

''Conclusion:'' Once the <math>D</math> from step 2 contains high enough powers, we can set <math>M^+ = M'</math>, as this will have unit determinant by multiplicativity. In each iteration, the effect of our algorithm was multiplication by <math>D\cdot E \cdot D^{-1} \cdot P</math>. Since the powers in <math>D</math> are descending and <math>E</math> is lower triangular, we find that <math>D\cdot E \cdot D^{-1}</math> contains only negative powers of <math>z</math>. Furthermore, by multiplicativity of the determinant again, we find that <math>\operatorname{det}(D\cdot E \cdot D^{-1}\cdot P) = \pm \operatorname{det} E \in \mathbb C\setminus \{0\}</math>. Thus we may take the product of these matrices obtained from all the iterations and set <math>M^-</math> to be its inverse.

Finally, recalling step 1, we have now decomposed <math>z^mM = M^-\cdot D \cdot M^+</math>. Dividing through with <math>z^m</math> and setting <math>M^0 = D\cdot z^{-m}</math> gives the result.

'''Example:''' Consider <math>M=\left(\begin{smallmatrix}1+z & z^{-1}+2 \\ z & 2\end{smallmatrix}\right)</math>. The determinant is 1. The first step is done by replacing <math>M</math> by <math>zM</math> which has determinant <math>z^2</math> and so <math>d=2</math>.

The second step is <math>\left(\begin{smallmatrix}z+z^2 & 1+2z \\ z^2 & 2z\end{smallmatrix}\right)=\left(\begin{smallmatrix}0 & 1 \\ 1 & 0\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 0\\ 0 &1\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 2 \\ z+z^2 & 1+2z\end{smallmatrix}\right)</math>. The third step gives <math>\left(\begin{smallmatrix}z & 2 \\ z+z^2 & 1+2z\end{smallmatrix}\right)=\left(\begin{smallmatrix}1 & 0 \\ 1/2 & 1\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 2 \\ z/2+z^2 & 2z\end{smallmatrix}\right)</math>.

Returning the factored-out powers, we want to repeat step 2 on the matrix  <math>\left(\begin{smallmatrix}z^2 & 2z \\ z/2+z^2 & 2z\end{smallmatrix}\right)=\left(\begin{smallmatrix}z & 0 \\ 0 & 1\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 2 \\ z/2+z^2 & 2z\end{smallmatrix}\right)</math>. Here, we can factor as <math>\left(\begin{smallmatrix}z & 0 \\ 0 & z\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 2 \\ 1/2+z & 2\end{smallmatrix}\right)</math>, meeting our goal of <math>d = 2</math>. Compiling all these operations:

:<math>
zM=\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
z & 0\\
0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
1/2 & 1
\end{pmatrix}
\begin{pmatrix}
z^{-1} & 0 \\
0 & 1
\end{pmatrix}
\begin{pmatrix}
z & 0\\ 0 & z
\end{pmatrix}
\begin{pmatrix}
z & 2 \\
1/2+z & 2
\end{pmatrix}=\begin{pmatrix}
z^{-1}/2 & 1\\
1 & 0
\end{pmatrix}\begin{pmatrix}z & 0 \\ 0 & z\end{pmatrix}\begin{pmatrix}z & 2 \\ 1/2+z & 2\end{pmatrix}.
</math>

Therefore, dividing by <math>z</math>, <math>M=\left(\begin{smallmatrix}z^{-1}/2 & 1 \\ 1 & 0\end{smallmatrix}\right)\left(\begin{smallmatrix}
1 & 0 \\
0 & 1
\end{smallmatrix}\right)\left(\begin{smallmatrix}z & 2 \\ 1/2+z & 2\end{smallmatrix}\right)</math>.

==See also==
*[Birkhoff decomposition (disambiguation)](/source/Birkhoff_decomposition_(disambiguation))
*[Riemann–Hilbert problem](/source/Riemann%E2%80%93Hilbert_problem)

== Notes ==
{{Reflist|30em}}

==References==
*{{Citation | last=Birkhoff | first=George David | author-link=George David Birkhoff | title=Singular points of ordinary linear differential equations | jstor=1988594 | jfm=40.0352.02 | year=1909 | journal=[Transactions of the American Mathematical Society](/source/Transactions_of_the_American_Mathematical_Society) | issn=0002-9947 | volume=10 | issue=4 | pages=436–470 | doi=10.2307/1988594| doi-access=free }}
*{{Citation | last1=Clancey | first1=K. | last2=Gohberg | first2=I. | title=Factorization of Matrix Functions and Singular Integral Operators | publisher=Springer | year=1981 | isbn=978-3-0348-5494-8 |  doi=10.1007/978-3-0348-5492-4| doi-access=free }}
*{{Citation | last=Grothendieck | first=Alexander | author-link=Alexander Grothendieck | title=Sur la classification des fibrés holomorphes sur la sphère de Riemann | jstor=2372388 | mr=0087176 | year=1957 | journal=[American Journal of Mathematics](/source/American_Journal_of_Mathematics) | issn=0002-9327 | volume=79 | issue=1 | pages=121–138 | doi=10.2307/2372388}}
*{{eom|title=Birkhoff factorization|first=G. |last=Khimshiashvili}}
*{{Citation | last1=Pressley | first1=Andrew | last2=Segal | first2=Graeme | title=Loop groups | url=https://books.google.com/books?id=MbFBXyuxLKgC | publisher=The Clarendon Press Oxford University Press | series=Oxford Mathematical Monographs | isbn=978-0-19-853535-5 | mr=900587 | year=1986}}

Category:Matrices (mathematics)

---
Adapted from the Wikipedia article [Birkhoff factorization](https://en.wikipedia.org/wiki/Birkhoff_factorization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Birkhoff_factorization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.