# Canonical basis

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 ${\mathcal {Z}}:=\mathbb {Z} \left[v,v^{-1}\right]$ with its two subrings ${\mathcal {Z}}^{\pm }:=\mathbb {Z} \left[v^{\pm 1}\right]$ and the automorphism ${\overline {\cdot }}$ defined by ${\overline {v}}:=v^{-1}$.
A precanonical structure on a free ${\mathcal {Z}}$-module $F$ consists of
* A standard basis $(t_{i})_{i\in I}$ of $F$,
* An interval finite partial order on $I$, that is, $(-\infty ,i]:=\{j\in I\mid j\leq i\}$ is finite for all $i\in I$,
* A dualization operation, that is, a bijection $F\to F$ of order two that is ${\overline {\cdot }}$-semilinear and will be denoted by ${\overline {\cdot }}$ as well.
If a precanonical structure is given, then one can define the ${\mathcal {Z}}^{\pm }$ submodule F$^±$:=∑Z$^±$t$_j${\textstyle F^{\pm }:=\sum {\mathcal {Z}}^{\pm }t_{j}} of $F$.
A canonical basis of the precanonical structure is then a ${\mathcal {Z}}$-basis $(c_{i})_{i\in I}$ of $F$ that satisfies:
* ${\overline {c_{i}}}=c_{i}$ and
* $c_{i}\in \sum _{j\leq i}{\mathcal {Z}}^{+}t_{j}{\text{ and }}c_{i}\equiv t_{i}\mod vF^{+}$
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 {\mathcal {Z}}$ defined by t$_j$$^¯$=∑$_i$r$_{ij}$t$_i${\textstyle {\overline {t_{j}}}=\sum _{i}r_{ij}t_{i}} satisfy $r_{ii}=1$ and $r_{ij}\neq 0\implies i\leq j$.
A canonical basis induces an isomorphism from $\textstyle F^{+}\cap {\overline {F^{+}}}=\sum _{i}\mathbb {Z} c_{i}$ to $F^{+}/vF^{+}$.

### 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}'=\sum _{y\leq 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 {x} _{m-1},\mathbf {x} _{m-2},\ldots ,\mathbf {x} _{1}$ that are in the Jordan chain generated by $\mathbf {x} _{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},\ldots ,(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}=\operatorname {rank} (A-\lambda _{i}I)^{k-1}-\operatorname {rank} (A-\lambda _{i}I)^{k}\qquad (k=1,2,\ldots ,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
    $\operatorname {rank} (A-\lambda _{i}I)^{0}=\operatorname {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={\begin{pmatrix}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{pmatrix}}$
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}=\operatorname {rank} (A-4I)^{3}-\operatorname {rank} (A-4I)^{4}=3-2=1,$
    $\rho _{3}=\operatorname {rank} (A-4I)^{2}-\operatorname {rank} (A-4I)^{3}=4-3=1,$
    $\rho _{2}=\operatorname {rank} (A-4I)^{1}-\operatorname {rank} (A-4I)^{2}=5-4=1,$
    $\rho _{1}=\operatorname {rank} (A-4I)^{0}-\operatorname {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}=\operatorname {rank} (A-5I)^{1}-\operatorname {rank} (A-5I)^{2}=5-4=1,$
    $\rho _{1}=\operatorname {rank} (A-5I)^{0}-\operatorname {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
    $\left\{\mathbf {x} _{1},\mathbf {x} _{2},\mathbf {x} _{3},\mathbf {x} _{4},\mathbf {y} _{1},\mathbf {y} _{2}\right\}=\left\{{\begin{pmatrix}-4\\0\\0\\0\\0\\0\end{pmatrix}},{\begin{pmatrix}-27\\-4\\0\\0\\0\\0\end{pmatrix}},{\begin{pmatrix}25\\-25\\-2\\0\\0\\0\end{pmatrix}},{\begin{pmatrix}0\\36\\-12\\-2\\2\\-1\end{pmatrix}},{\begin{pmatrix}3\\2\\1\\1\\0\\0\end{pmatrix}},{\begin{pmatrix}-8\\-4\\-1\\0\\1\\0\end{pmatrix}}\right\}.$
$\mathbf {x} _{1}$ is the ordinary eigenvector associated with $\lambda _{1}$.
$\mathbf {x} _{2},\mathbf {x} _{3}$ and $\mathbf {x} _{4}$ are generalized eigenvectors associated with $\lambda _{1}$.
$\mathbf {y} _{1}$ is the ordinary eigenvector associated with $\lambda _{2}$.
$\mathbf {y} _{2}$ is a generalized eigenvector associated with $\lambda _{2}$.
A matrix $J$ in Jordan normal form, similar to $A$ is obtained as follows:
    $M={\begin{pmatrix}\mathbf {x} _{1}&\mathbf {x} _{2}&\mathbf {x} _{3}&\mathbf {x} _{4}&\mathbf {y} _{1}&\mathbf {y} _{2}\end{pmatrix}}={\begin{pmatrix}-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{pmatrix}},$
    $J={\begin{pmatrix}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{pmatrix}},$
where the matrix $M$ is a generalized modal matrix for $A$ and $AM=MJ$.