Canonical basis

Template:Short description In mathematics, a canonical basis is a basis of an algebraic structure that is canonical in a sense that depends on the precise context:

• In a coordinate space, and more generally in a free module, it refers to the standard basis defined by the Kronecker delta.
• In a polynomial ring, it refers to its standard basis given by the monomials, $(X^i{)}_i$.
• For finite extension fields, it means the polynomial basis.
• In linear algebra, it refers to a set of n linearly independent generalized eigenvectors of an n×n matrix $A$, if the set is composed entirely of Jordan chains.
• In representation theory, it refers to the basis of the quantum groups introduced by Lusztig.

Representation theory

The canonical basis for the irreducible representations of a quantized enveloping algebra of type $ADE$ and also for the plus part of that algebra was introduced by Lusztig by two methods: an algebraic one (using a braid group action and PBW bases) and a topological one (using intersection cohomology). Specializing the parameter $q$ to $q=1$ yields a canonical basis for the irreducible representations of the corresponding simple Lie algebra, which was not known earlier. Specializing the parameter $q$ to $q=0$ yields something like a shadow of a basis. This shadow (but not the basis itself) for the case of irreducible representations was considered independently by Kashiwara; it is sometimes called the crystal basis. The definition of the canonical basis was extended to the Kac-Moody setting by Kashiwara (by an algebraic method) and by Lusztig (by a topological method).

There is a general concept underlying these bases:

Consider the ring of integral Laurent polynomials $𝒵:=\mathbb{Z}[v,v^{-1}]$ with its two subrings ${𝒵}^{\pm }:=\mathbb{Z}\left[v^{\pm 1}\right]$ and the automorphism $\bar{\cdot }$ defined by $\bar{v}:=v^{-1}$.

A precanonical structure on a free $𝒵$-module $F$ consists of

• A standard basis $(t_i{)}_{i\in I}$ of $F$,
• An interval finite partial order on $I$, that is, $(-\mathrm{\infty },i]:=\{j\in I\mid j\le i\}$ is finite for all $i\in I$,
• A dualization operation, that is, a bijection $F\to F$ of order two that is $\bar{\cdot }$-semilinear and will be denoted by $\bar{\cdot }$ as well.

If a precanonical structure is given, then one can define the ${𝒵}^{\pm }$ submodule $F^{\pm }:=\sum {𝒵}^{\pm }{t}_j$ of $F$.

A canonical basis of the precanonical structure is then a $𝒵$-basis $(c_i{)}_{i\in I}$ of $F$ that satisfies:

• $\overline{c_i}=c_i$ and
• $c_i\in \sum _{j\le i}{𝒵}^{+}{t}_j\text{ and }{c}_i\equiv t_{i}modv{F}^{+}$

for all $i\in I$.

One can show that there exists at most one canonical basis for each precanonical structure. A sufficient condition for existence is that the polynomials $r_{ij}\in 𝒵$ defined by $\overline{t_j}={\sum }_i{r}_{ij}{t}_i$ satisfy $r_{ii}=1$ and $r_{ij}\ne 0⟹i\le j$.

A canonical basis induces an isomorphism from $F^{+}\cap \overline{F^{+}}={\sum }_i\mathbb{Z}{c}_i$ to $F^{+}/v{F}^{+}$.

Hecke algebras

Let $(W,S)$ be a Coxeter group. The corresponding Iwahori-Hecke algebra $H$ has the standard basis $(T_w{)}_{w\in W}$, the group is partially ordered by the Bruhat order which is interval finite and has a dualization operation defined by $\overline{T_w}:=T_{w^{-1}}^{-1}$. This is a precanonical structure on $H$ that satisfies the sufficient condition above and the corresponding canonical basis of $H$ is the Kazhdan–Lusztig basis

${C_w}^{\prime }=\sum _{y\le w}{P}_{y,w}(v^2)T_w$

with $P_{y,w}$ being the Kazhdan–Lusztig polynomials.

Linear algebra

If we are given an n × n matrix $A$ and wish to find a matrix $J$ in Jordan normal form, similar to $A$, we are interested only in sets of linearly independent generalized eigenvectors. A matrix in Jordan normal form is an "almost diagonal matrix," that is, as close to diagonal as possible. A diagonal matrix $D$ is a special case of a matrix in Jordan normal form. An ordinary eigenvector is a special case of a generalized eigenvector.

Every n × n matrix $A$ possesses n linearly independent generalized eigenvectors. Generalized eigenvectors corresponding to distinct eigenvalues are linearly independent. If $\lambda$ is an eigenvalue of $A$ of algebraic multiplicity $\mu$, then $A$ will have $\mu$ linearly independent generalized eigenvectors corresponding to $\lambda$.

For any given n × n matrix $A$, there are infinitely many ways to pick the n linearly independent generalized eigenvectors. If they are chosen in a particularly judicious manner, we can use these vectors to show that $A$ is similar to a matrix in Jordan normal form. In particular,

Definition: A set of n linearly independent generalized eigenvectors is a canonical basis if it is composed entirely of Jordan chains.

Thus, once we have determined that a generalized eigenvector of rank m is in a canonical basis, it follows that the m − 1 vectors ${𝐱}_{m-1},{𝐱}_{m-2},\dots ,{𝐱}_1$ that are in the Jordan chain generated by ${𝐱}_m$ are also in the canonical basis.

Computation

Let ${\lambda }_i$ be an eigenvalue of $A$ of algebraic multiplicity ${\mu }_i$. First, find the ranks (matrix ranks) of the matrices $(A-{\lambda }_{i}I),(A-{\lambda }_{i}I{)}^2,\dots ,(A-{\lambda }_{i}I{)}^{m_i}$. The integer $m_i$ is determined to be the first integer for which $(A-{\lambda }_{i}I{)}^{m_i}$ has rank $n-{\mu }_i$ (n being the number of rows or columns of $A$, that is, $A$ is n × n).

Now define

${\rho }_k=\mathrm{rank}(A-{\lambda }_{i}I{)}^{k-1}-\mathrm{rank}(A-{\lambda }_{i}I{)}^k(k=1,2,\dots ,m_i).$

The variable ${\rho }_k$ designates the number of linearly independent generalized eigenvectors of rank k (generalized eigenvector rank; see generalized eigenvector) corresponding to the eigenvalue ${\lambda }_i$ that will appear in a canonical basis for $A$. Note that

$\mathrm{rank}(A-{\lambda }_{i}I{)}^0=\mathrm{rank}(I)=n.$

Once we have determined the number of generalized eigenvectors of each rank that a canonical basis has, we can obtain the vectors explicitly (see generalized eigenvector).

Example

This example illustrates a canonical basis with two Jordan chains. Unfortunately, it is a little difficult to construct an interesting example of low order. The matrix

$A=\left(\begin{array}{cccccc}4& 1& 1& 0& 0& -1\\ 0& 4& 2& 0& 0& 1\\ 0& 0& 4& 1& 0& 0\\ 0& 0& 0& 5& 1& 0\\ 0& 0& 0& 0& 5& 2\\ 0& 0& 0& 0& 0& 4\end{array}\right)$

has eigenvalues ${\lambda }_1=4$ and ${\lambda }_2=5$ with algebraic multiplicities ${\mu }_1=4$ and ${\mu }_2=2$, but geometric multiplicities ${\gamma }_1=1$ and ${\gamma }_2=1$.

For ${\lambda }_1=4,$ we have $n-{\mu }_1=6-4=2,$

$(A-4I)$ has rank 5,

$(A-4I{)}^2$ has rank 4,

$(A-4I{)}^3$ has rank 3,

$(A-4I{)}^4$ has rank 2.

Therefore $m_1=4.$

${\rho }_4=\mathrm{rank}(A-4I{)}^3-\mathrm{rank}(A-4I{)}^4=3-2=1,$

${\rho }_3=\mathrm{rank}(A-4I{)}^2-\mathrm{rank}(A-4I{)}^3=4-3=1,$

${\rho }_2=\mathrm{rank}(A-4I{)}^1-\mathrm{rank}(A-4I{)}^2=5-4=1,$

${\rho }_1=\mathrm{rank}(A-4I{)}^0-\mathrm{rank}(A-4I{)}^1=6-5=1.$

Thus, a canonical basis for $A$ will have, corresponding to ${\lambda }_1=4,$ one generalized eigenvector each of ranks 4, 3, 2 and 1.

For ${\lambda }_2=5,$ we have $n-{\mu }_2=6-2=4,$

$(A-5I)$ has rank 5,

$(A-5I{)}^2$ has rank 4.

Therefore $m_2=2.$

${\rho }_2=\mathrm{rank}(A-5I{)}^1-\mathrm{rank}(A-5I{)}^2=5-4=1,$

${\rho }_1=\mathrm{rank}(A-5I{)}^0-\mathrm{rank}(A-5I{)}^1=6-5=1.$

Thus, a canonical basis for $A$ will have, corresponding to ${\lambda }_2=5,$ one generalized eigenvector each of ranks 2 and 1.

A canonical basis for $A$ is

$\{{𝐱}_1,{𝐱}_2,{𝐱}_3,{𝐱}_4,{𝐲}_1,{𝐲}_2\}=\{\left(\begin{array}{c}-4\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}-27\\ -4\\ 0\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}25\\ -25\\ -2\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 36\\ -12\\ -2\\ 2\\ -1\end{array}\right),\left(\begin{array}{c}3\\ 2\\ 1\\ 1\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}-8\\ -4\\ -1\\ 0\\ 1\\ 0\end{array}\right)\}.$

${𝐱}_1$ is the ordinary eigenvector associated with ${\lambda }_1$. ${𝐱}_2,{𝐱}_3$ and ${𝐱}_4$ are generalized eigenvectors associated with ${\lambda }_1$. ${𝐲}_1$ is the ordinary eigenvector associated with ${\lambda }_2$. ${𝐲}_2$ is a generalized eigenvector associated with ${\lambda }_2$.

A matrix $J$ in Jordan normal form, similar to $A$ is obtained as follows:

$M=\left(\begin{array}{cccccc}{𝐱}_1& {𝐱}_2& {𝐱}_3& {𝐱}_4& {𝐲}_1& {𝐲}_2\end{array}\right)=\left(\begin{array}{cccccc}-4& -27& 25& 0& 3& -8\\ 0& -4& -25& 36& 2& -4\\ 0& 0& -2& -12& 1& -1\\ 0& 0& 0& -2& 1& 0\\ 0& 0& 0& 2& 0& 1\\ 0& 0& 0& -1& 0& 0\end{array}\right),$

$J=\left(\begin{array}{cccccc}4& 1& 0& 0& 0& 0\\ 0& 4& 1& 0& 0& 0\\ 0& 0& 4& 1& 0& 0\\ 0& 0& 0& 4& 0& 0\\ 0& 0& 0& 0& 5& 1\\ 0& 0& 0& 0& 0& 5\end{array}\right),$

where the matrix $M$ is a generalized modal matrix for $A$ and $AM=MJ$.

See also

• Canonical form
• Change of basis
• Normal basis
• Normal form (disambiguation)
• Polynomial basis

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation