Birkhoff factorization

In mathematics, Birkhoff factorization or Birkhoff decomposition, introduced by George David Birkhoff (1909), is a generalization of the LU decomposition (i.e. Gauss elimination) to loop groups.

The factorization of an invertible matrix ${\displaystyle M\in \mathrm {GL} _{n}(\mathbb {C} [z,z^{-1}])}$ with coefficients that are Laurent polynomials in ${\displaystyle z}$ is given by a product ${\displaystyle M=M^{+}M^{0}M^{-}}$, where ${\displaystyle M^{+}}$ has entries that are polynomials in ${\displaystyle z}$, ${\displaystyle M^{0}=\mathrm {diag} (z^{k_{1}},z^{k_{2}},...,z^{k_{n}})}$ is diagonal with ${\displaystyle k_{i}\in \mathbb {Z} }$ for ${\displaystyle 1\leq i\leq n}$ and ${\displaystyle k_{1}\geq k_{2}\geq ...\geq k_{n}}$, and ${\displaystyle M^{-}}$ has entries that are polynomials in ${\displaystyle z^{-1}}$. For a generic matrix we have ${\displaystyle M^{0}=\mathrm {id} }$.

Birkhoff factorization implies the Birkhoff–Grothendieck theorem of Grothendieck (1957) that vector bundles over the projective line are sums of line bundles.

There are several variations where the general linear group is replaced by some other reductive algebraic group, due to Alexander Grothendieck (1957). Birkhoff factorization follows from the Bruhat decomposition for affine Kac–Moody groups (or loop groups), and conversely the Bruhat decomposition for the affine general linear group follows from Birkhoff factorization together with the Bruhat decomposition for the ordinary general linear group.

There is an effective algorithm to compute the Birkhoff factorization. The following will be based on the book by Clancey-Gohberg,¹ where a more general case can also be found.

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

First step: Replace ${\displaystyle M}$ by ${\displaystyle z^{m}M}$ to cancel any denominators, i.e. so that ${\displaystyle z^{m}M}$ is defined over ${\displaystyle \mathbb {C} [z]}$. Let ${\displaystyle d=\operatorname {ord} _{z}\operatorname {det} z^{m}M}$ be the exponent at ${\displaystyle z}$, note that this is now nonnegative.

Second step: Permute the rows and factor out the highest possible power of ${\displaystyle z}$ in each row, while staying over ${\displaystyle \mathbb {C} [z]}$. The permutation has to ensure that the highest powers of ${\displaystyle z}$ are decreasing. Denote ${\displaystyle P,D}$ the permutation matrix, and the diagonal matrix of the powers, respectively.

${\displaystyle M'=D^{-1}\cdot P\cdot M}$

Third step: If the sum of the powers from step 2 equals ${\displaystyle d}$, we are done. Otherwise, perform row operations without pivoting such that at least one row becomes zero modulo ${\displaystyle z}$. Put the factored powers back into our matrix and return to step 2.

By disallowing pivoting, we are asking that the matrix ${\displaystyle E\in \mathrm {GL} _{n}(\mathbb {C} )}$ encoding the row operations is lower triangular.

The matrix to be returned to step 2 is:

${\displaystyle M''=D\cdot E\cdot M'}$

Note that as long as the determinant of the matrix is not constant, the determinant is zero modulo ${\displaystyle z}$, hence the rows are linearly dependent modulo ${\displaystyle z}$. Therefore, this step can be carried out.

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

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

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

The second step is ${\displaystyle \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)}$. The third step gives ${\displaystyle \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)}$.

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

${\displaystyle 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}}.}$

Therefore, dividing by ${\displaystyle z}$, ${\displaystyle 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)}$.