Английская Википедия:Canonical basis
Шаблон: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, <math>(X^i)_i</math>.
- 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 <math>A</math>, if the set is composed entirely of Jordan chains.[1]
- 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 <math>ADE</math> and also for the plus part of that algebra was introduced by Lusztig [2] by two methods: an algebraic one (using a braid group action and PBW bases) and a topological one (using intersection cohomology). Specializing the parameter <math>q</math> to <math>q=1</math> yields a canonical basis for the irreducible representations of the corresponding simple Lie algebra, which was not known earlier. Specializing the parameter <math>q</math> to <math>q=0</math> 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;[3] it is sometimes called the crystal basis. The definition of the canonical basis was extended to the Kac-Moody setting by Kashiwara [4] (by an algebraic method) and by Lusztig [5] (by a topological method).
There is a general concept underlying these bases:
Consider the ring of integral Laurent polynomials <math>\mathcal{Z}:=\mathbb{Z}\left[v,v^{-1}\right]</math> with its two subrings <math>\mathcal{Z}^{\pm}:=\mathbb{Z}\left[v^{\pm 1}\right]</math> and the automorphism <math>\overline{\cdot}</math> defined by <math>\overline{v}:=v^{-1}</math>.
A precanonical structure on a free <math>\mathcal{Z}</math>-module <math>F</math> consists of
- A standard basis <math>(t_i)_{i\in I}</math> of <math>F</math>,
- An interval finite partial order on <math>I</math>, that is, <math>(-\infty,i] := \{j\in I \mid j\leq i\}</math> is finite for all <math>i\in I</math>,
- A dualization operation, that is, a bijection <math>F\to F</math> of order two that is <math>\overline{\cdot}</math>-semilinear and will be denoted by <math>\overline{\cdot}</math> as well.
If a precanonical structure is given, then one can define the <math>\mathcal{Z}^{\pm}</math> submodule <math display="inline">F^{\pm} := \sum \mathcal{Z}^{\pm} t_j</math> of <math>F</math>.
A canonical basis of the precanonical structure is then a <math>\mathcal{Z}</math>-basis <math>(c_i)_{i\in I}</math> of <math>F</math> that satisfies:
- <math>\overline{c_i}=c_i</math> and
- <math>c_i \in \sum_{j\leq i} \mathcal{Z}^+ t_j \text{ and } c_i \equiv t_i \mod vF^+</math>
for all <math>i\in I</math>.
One can show that there exists at most one canonical basis for each precanonical structure.[6] A sufficient condition for existence is that the polynomials <math>r_{ij}\in\mathcal{Z}</math> defined by <math display="inline">\overline{t_j}=\sum_i r_{ij} t_i</math> satisfy <math>r_{ii}=1</math> and <math>r_{ij}\neq 0 \implies i\leq j</math>.
A canonical basis induces an isomorphism from <math>\textstyle F^+\cap \overline{F^+} = \sum_i \mathbb{Z}c_i</math> to <math>F^+/vF^+</math>.
Hecke algebras
Let <math>(W,S)</math> be a Coxeter group. The corresponding Iwahori-Hecke algebra <math>H</math> has the standard basis <math>(T_w)_{w\in W}</math>, the group is partially ordered by the Bruhat order which is interval finite and has a dualization operation defined by <math>\overline{T_w}:=T_{w^{-1}}^{-1}</math>. This is a precanonical structure on <math>H</math> that satisfies the sufficient condition above and the corresponding canonical basis of <math>H</math> is the Kazhdan–Lusztig basis
- <math>C_w' = \sum_{y\leq w} P_{y,w}(v^2) T_w</math>
with <math>P_{y,w}</math> being the Kazhdan–Lusztig polynomials.
Linear algebra
If we are given an n × n matrix <math>A</math> and wish to find a matrix <math>J</math> in Jordan normal form, similar to <math>A</math>, 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 <math>D</math> 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 <math>A</math> possesses n linearly independent generalized eigenvectors. Generalized eigenvectors corresponding to distinct eigenvalues are linearly independent. If <math>\lambda</math> is an eigenvalue of <math>A</math> of algebraic multiplicity <math>\mu</math>, then <math>A</math> will have <math>\mu</math> linearly independent generalized eigenvectors corresponding to <math>\lambda</math>.
For any given n × n matrix <math>A</math>, 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 <math>A</math> 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 <math> \mathbf x_{m-1}, \mathbf x_{m-2}, \ldots , \mathbf x_1 </math> that are in the Jordan chain generated by <math> \mathbf x_m </math> are also in the canonical basis.[7]
Computation
Let <math> \lambda_i </math> be an eigenvalue of <math>A</math> of algebraic multiplicity <math> \mu_i </math>. First, find the ranks (matrix ranks) of the matrices <math> (A - \lambda_i I), (A - \lambda_i I)^2, \ldots , (A - \lambda_i I)^{m_i} </math>. The integer <math>m_i</math> is determined to be the first integer for which <math> (A - \lambda_i I)^{m_i} </math> has rank <math>n - \mu_i </math> (n being the number of rows or columns of <math>A</math>, that is, <math>A</math> is n × n).
Now define
- <math> \rho_k = \operatorname{rank}(A - \lambda_i I)^{k-1} - \operatorname{rank}(A - \lambda_i I)^k \qquad (k = 1, 2, \ldots , m_i).</math>
The variable <math> \rho_k </math> designates the number of linearly independent generalized eigenvectors of rank k (generalized eigenvector rank; see generalized eigenvector) corresponding to the eigenvalue <math> \lambda_i </math> that will appear in a canonical basis for <math>A</math>. Note that
- <math> \operatorname{rank}(A - \lambda_i I)^0 = \operatorname{rank}(I) = n .</math>
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).[8]
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.[9] The matrix
- <math>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}</math>
has eigenvalues <math> \lambda_1 = 4 </math> and <math> \lambda_2 = 5 </math> with algebraic multiplicities <math> \mu_1 = 4 </math> and <math> \mu_2 = 2 </math>, but geometric multiplicities <math> \gamma_1 = 1 </math> and <math> \gamma_2 = 1 </math>.
For <math> \lambda_1 = 4,</math> we have <math> n - \mu_1 = 6 - 4 = 2, </math>
- <math> (A - 4I) </math> has rank 5,
- <math> (A - 4I)^2 </math> has rank 4,
- <math> (A - 4I)^3 </math> has rank 3,
- <math> (A - 4I)^4 </math> has rank 2.
Therefore <math>m_1 = 4.</math>
- <math> \rho_4 = \operatorname{rank}(A - 4I)^3 - \operatorname{rank}(A - 4I)^4 = 3 - 2 = 1,</math>
- <math> \rho_3 = \operatorname{rank}(A - 4I)^2 - \operatorname{rank}(A - 4I)^3 = 4 - 3 = 1,</math>
- <math> \rho_2 = \operatorname{rank}(A - 4I)^1 - \operatorname{rank}(A - 4I)^2 = 5 - 4 = 1,</math>
- <math> \rho_1 = \operatorname{rank}(A - 4I)^0 - \operatorname{rank}(A - 4I)^1 = 6 - 5 = 1.</math>
Thus, a canonical basis for <math>A</math> will have, corresponding to <math> \lambda_1 = 4,</math> one generalized eigenvector each of ranks 4, 3, 2 and 1.
For <math> \lambda_2 = 5,</math> we have <math> n - \mu_2 = 6 - 2 = 4, </math>
- <math> (A - 5I) </math> has rank 5,
- <math> (A - 5I)^2 </math> has rank 4.
Therefore <math>m_2 = 2.</math>
- <math> \rho_2 = \operatorname{rank}(A - 5I)^1 - \operatorname{rank}(A - 5I)^2 = 5 - 4 = 1,</math>
- <math> \rho_1 = \operatorname{rank}(A - 5I)^0 - \operatorname{rank}(A - 5I)^1 = 6 - 5 = 1.</math>
Thus, a canonical basis for <math>A</math> will have, corresponding to <math> \lambda_2 = 5,</math> one generalized eigenvector each of ranks 2 and 1.
A canonical basis for <math>A</math> is
- <math>
\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\}. </math>
<math> \mathbf x_1 </math> is the ordinary eigenvector associated with <math> \lambda_1 </math>. <math> \mathbf x_2, \mathbf x_3 </math> and <math> \mathbf x_4 </math> are generalized eigenvectors associated with <math> \lambda_1 </math>. <math> \mathbf y_1 </math> is the ordinary eigenvector associated with <math> \lambda_2 </math>. <math> \mathbf y_2 </math> is a generalized eigenvector associated with <math> \lambda_2 </math>.
A matrix <math>J</math> in Jordan normal form, similar to <math>A</math> is obtained as follows:
- <math>
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}, </math>
- <math> 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}, </math>
where the matrix <math>M</math> is a generalized modal matrix for <math>A</math> and <math>AM = MJ</math>.[10]
See also
Notes
References
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation