Canonical basis - Misplaced Pages

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 ${\mathcal {Z}}:=\mathbb {Z} \left$ with its two subrings ${\mathcal {Z}}^{\pm }:=\mathbb {Z} \left$ 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 ${\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 ${\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}$ .