Canonical basis

Short description: Basis of a type of algebraic structure

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{\mathbb{Z}}[v,v^{-1}]$ with its two subrings ${{𝒵}}^{\pm }:=\mathbb{\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{\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 ${\mathbf{𝐱}}_{m-1},{\mathbf{𝐱}}_{m-2},\dots ,{\mathbf{𝐱}}_1$ that are in the Jordan chain generated by ${\mathbf{𝐱}}_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

$\{{\mathbf{𝐱}}_1,{\mathbf{𝐱}}_2,{\mathbf{𝐱}}_3,{\mathbf{𝐱}}_4,{\mathbf{𝐲}}_1,{\mathbf{𝐲}}_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)\}.$

${\mathbf{𝐱}}_1$ is the ordinary eigenvector associated with ${\lambda }_1$. ${\mathbf{𝐱}}_2,{\mathbf{𝐱}}_3$ and ${\mathbf{𝐱}}_4$ are generalized eigenvectors associated with ${\lambda }_1$. ${\mathbf{𝐲}}_1$ is the ordinary eigenvector associated with ${\lambda }_2$. ${\mathbf{𝐲}}_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}{\mathbf{𝐱}}_1& {\mathbf{𝐱}}_2& {\mathbf{𝐱}}_3& {\mathbf{𝐱}}_4& {\mathbf{𝐲}}_1& {\mathbf{𝐲}}_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

• Bronson, Richard (1970), Matrix Methods: An Introduction, New York: Academic Press 
• Deng, Bangming; Ju, Jie; Parshall, Brian; Wang, Jianpan (2008), Finite Dimensional Algebras and Quantum Groups, Mathematical surveys and monographs, 150, Providence, R.I.: American Mathematical Society, ISBN 9780821875315, https://books.google.com/books?id=k9aUvxN2w2MC 
• Kashiwara, Masaki (1990), "Crystalizing the q-analogue of universal enveloping algebras", Communications in Mathematical Physics 133 (2): 249–260, doi:10.1007/bf02097367, ISSN 0010-3616, Bibcode: 1990CMaPh.133..249K, https://projecteuclid.org/journals/communications-in-mathematical-physics/volume-133/issue-2/Crystalizing-the-q-analogue-of-universal-enveloping-algebras/cmp/1104201397.full 
• Kashiwara, Masaki (1991), "On crystal bases of the q-analogue of universal enveloping algebras", Duke Mathematical Journal 63 (2): 465–516, doi:10.1215/S0012-7094-91-06321-0, ISSN 0012-7094, https://doi.org/10.1215/S0012-7094-91-06321-0 
• Lusztig, George (1990), "Canonical bases arising from quantized enveloping algebras", Journal of the American Mathematical Society 3 (2): 447–498, doi:10.2307/1990961, ISSN 0894-0347 
• Lusztig, George (1991), "Quivers, perverse sheaves and quantized enveloping algebras", Journal of the American Mathematical Society 4 (2): 365–421, doi:10.2307/2939279, ISSN 0894-0347 
• Lusztig, George (1993), Introduction to quantum groups, Boston, MA: Birkhauser Boston, ISBN 0-8176-3712-5 
• Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: Wiley