Editing 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 [[monomial]]s, <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 eigenvector]]s of an ''n''×''n'' matrix <math>A</math>, if the set is composed entirely of [[Jordan chain]]s.<ref>{{harvtxt|Bronson|1970|p=196}}</ref>
* 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 <ref>{{harvtxt|Lusztig|1990}}</ref> 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;<ref>{{harvtxt|Kashiwara|1990}}</ref> it is sometimes called the [[crystal basis]].
The definition of the canonical basis was extended to the Kac-Moody setting by Kashiwara <ref>{{harvtxt|Kashiwara|1991}}</ref> (by an algebraic method) and by Lusztig <ref>{{harvtxt|Lusztig|1991}}</ref> (by a topological method).

There is a general concept underlying these bases:

Consider the ring of integral [[Laurent polynomial]]s <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 map|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.<ref>{{harvtxt|Lusztig|1993|p=194}}</ref> 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 polynomial]]s.

==Linear algebra==
If we are given an ''n'' × ''n'' [[matrix (mathematics)|matrix]] <math>A</math> and wish to find a matrix <math>J</math> in [[Jordan normal form]], [[matrix similarity|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 [[eigenvector|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 [[generalized eigenvector#Overview and definition|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.<ref>{{harvtxt|Bronson|1970|pp=196,197}}</ref>

===Computation===
Let <math> \lambda_i </math> be an eigenvalue of <math>A</math> of algebraic multiplicity <math> \mu_i </math>.  First, find the [[rank (linear algebra)|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#Overview and definition|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#Computation of generalized eigenvectors|generalized eigenvector]]).<ref>{{harvtxt|Bronson|1970|pp=197,198}}</ref>

===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.<ref>{{harvtxt|Nering|1970|pp=122,123}}</ref>
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 multiplicity|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>.<ref>{{harvtxt|Bronson|1970|p=203}}</ref>

==See also==
* [[Canonical form]]
* [[Change of basis]]
* [[Normal basis]]
* [[Normal form (mathematics)|Normal form (disambiguation)]]
* [[Polynomial basis]]

== Notes ==
<references/>

==References==
* {{ citation | first1 = Richard | last1 = Bronson | year = 1970 | lccn = 70097490 | title = Matrix Methods: An Introduction | publisher = [[Academic Press]] | location = New York }}
* {{Citation |last1 = Deng |first1 = Bangming |last2 = Ju |first2 = Jie |last3 = Parshall |first3 = Brian |last4 = Wang |first4 = Jianpan |title = Finite Dimensional Algebras and Quantum Groups |url = https://books.google.com/books?id=k9aUvxN2w2MC |publisher = [[American Mathematical Society]] |location = Providence, R.I. |series = Mathematical surveys and monographs |isbn = 9780821875315 |year = 2008 |volume = 150 }}
*{{Citation | last1=Kashiwara | first1=Masaki | author1-link=Masaki Kashiwara | title=Crystalizing the q-analogue of universal enveloping algebras | url=https://projecteuclid.org/journals/communications-in-mathematical-physics/volume-133/issue-2/Crystalizing-the-q-analogue-of-universal-enveloping-algebras/cmp/1104201397.full | mr=1090425 | year=1990 | journal=Communications in Mathematical Physics | issn=0010-3616 | volume=133 | issue=2 | pages=249–260 | doi=10.1007/bf02097367| bibcode=1990CMaPh.133..249K | s2cid=121695684 | url-access=subscription }}
*{{Citation | last1=Kashiwara | first1=Masaki | author1-link=Masaki Kashiwara | title=On crystal bases of the q-analogue of universal enveloping algebras | url=https://doi.org/10.1215/S0012-7094-91-06321-0 | mr=1115118 | year=1991 | journal=Duke Mathematical Journal | issn=0012-7094 | volume=63 | issue=2 | pages=465–516 | doi=10.1215/S0012-7094-91-06321-0 | url-access=subscription }}
*{{Citation | last1=Lusztig | first1=George | author1-link=George Lusztig | title=Canonical bases arising from quantized enveloping algebras | doi=10.2307/1990961 | mr=1035415 | year=1990 | journal=[[Journal of the American Mathematical Society]] | issn=0894-0347 | volume=3 | issue=2 | pages=447–498| jstor=1990961 | doi-access=free }}
*{{Citation | last1=Lusztig | first1=George | author1-link=George Lusztig | title=Quivers, perverse sheaves and quantized enveloping algebras | doi=10.2307/2939279 | mr=1088333 | year=1991 | journal=[[Journal of the American Mathematical Society]] | issn=0894-0347 | volume=4 | issue=2 | pages=365–421| jstor=2939279 | doi-access=free }}
*{{Citation | last1=Lusztig | first1=George | author1-link=George Lusztig | year = 1993 | title = Introduction to quantum groups | publisher = Birkhauser Boston | location = Boston, MA | isbn=0-8176-3712-5 | mr=1227098}}
* {{ citation | first1 = Evar D. | last1 = Nering | year = 1970 | title = Linear Algebra and Matrix Theory | edition = 2nd | publisher = [[John Wiley & Sons|Wiley]] | location = New York | lccn = 76091646 }}

[[Category:Linear algebra]]
[[Category:Abstract algebra]]
[[Category:Lie algebras]]
[[Category:Representation theory]]
[[Category:Quantum groups]]