Canonical basis

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

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

Representation theory

In representation theory there are several basis that are called "canonical", e.g. Lusztig's canonical basis and closely related Kashiwara's crystal basis in quantum groups and their representations. There is a general concept underlying these basis:

Consider the ring of integral Laurent polynomials \mathcal{Z}:=\mathbb{Z}[v,v^{-1}] with its two subrings \mathcal{Z}^{\pm}:=\mathbb{Z}[v^{\pm 1}] and the automorphism \overline{\cdot} that is 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,
  • A partial order on I that is interval finite, i.e. (-\infty,i] := \{j\in I | j\leq i\} is finite for all i\in I,
  • A dualization operation, i.e. 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^{\pm} := \sum \mathcal{Z}^{\pm} t_j of F.

A canonical basis at v=0 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_jand c_i \equiv t_i \mod vF^+

for all i\in I. A canonical basis at v=\infty is analogously defined to be a basis (\widetilde{c}_i)_{i\in I} that satisfies

  • \overline{\widetilde{c}_i}=\widetilde{c}_i and
  • \widetilde{c}_i \in \sum_{j\leq i} \mathcal{Z}^- t_j and \widetilde{c}_i \equiv t_i \mod v^{-1}F^-

for all i\in I. The naming "at v=\infty" alludes to the fact \lim_{v\to\infty} v^{-1} =0 and hence the "specialization" v\mapsto\infty corresponds to quotienting out the relation v^{-1}=0.

One can show that there exists at most one canonical basis at v=0 (and at most one at v=\infty) for each precanonical structure. A sufficient condition for existence is that the polynomials r_{ij}\in\mathcal{Z} defined by \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 at v=0 (v=\infty) induces an isomorphism from \textstyle F^+\cap \overline{F^+} = \sum_i \mathbb{Z}c_i to F^+/vF^+ (\textstyle F^{-} \cap \overline{F^{-}}=\sum_i \mathbb{Z}\widetilde{c}_i \to F^{-}/v^{-1} F^{-} respectively).

Examples

Quantum groups

The canonical basis of quantum groups in the sense of Lusztig and Kashiwara are canonical basis at v=0.

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 at v=0 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  \bold x_{m-1}, \bold x_{m-2}, \ldots , \bold x_1 that are in the Jordan chain generated by  \bold x_m are also in the canonical basis.[2]

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 = rank(A - \lambda_i I)^{k-1} - 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

 rank(A - \lambda_i I)^0 = 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).[3]

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.[4] 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 = rank(A - 4I)^3 - rank(A - 4I)^4 = 3 - 2 = 1,
 \rho_3 = rank(A - 4I)^2 - rank(A - 4I)^3 = 4 - 3 = 1,
 \rho_2 = rank(A - 4I)^1 - rank(A - 4I)^2 = 5 - 4 = 1,
 \rho_1 = rank(A - 4I)^0 - 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 = rank(A - 5I)^1 - rank(A - 5I)^2 = 5 - 4 = 1,
 \rho_1 = rank(A - 5I)^0 - 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\{ \bold x_1, \bold x_2, \bold x_3, \bold x_4, \bold y_1, \bold 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\}.

 \bold x_1 is the ordinary eigenvector associated with  \lambda_1 .  \bold x_2, \bold x_3 and  \bold x_4 are generalized eigenvectors associated with  \lambda_1 .  \bold y_1 is the ordinary eigenvector associated with  \lambda_2 .  \bold 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} \bold x_1 & \bold x_2 & \bold x_3 & \bold x_4 & \bold y_1 & \bold 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.[5]

See also

Notes

  1. Bronson (1970, p. 196)
  2. Bronson (1970, pp. 196,197)
  3. Bronson (1970, pp. 197,198)
  4. Nering (1970, pp. 122,123)
  5. Bronson (1970, p. 203)

References

pt:Base canônica