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: Representation theory. The canonical basis for the irreducible representations of a quantized enveloping algebra of type formula_3 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 formula_4 to formula_5 yields a canonical basis for the irreducible representations of the corresponding simple Lie algebra, which was not  known earlier. Specializing the parameter formula_4 to formula_7 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 formula_8 with its two subrings formula_9 and the automorphism formula_10 defined by formula_11. A "precanonical structure" on a  free formula_12-module formula_13 consists of If a precanonical structure is given, then one can define the formula_22 submodule formula_23 of formula_13. A "canonical basis of the precanonical structure is then a formula_12-basis formula_26 of formula_13 that satisfies: for all formula_18. One can show that there exists at most one canonical basis for each precanonical structure. A sufficient condition for existence is that the polynomials formula_31 defined by formula_32 satisfy formula_33 and formula_34. A canonical basis induces an isomorphism from formula_35 to formula_36. Hecke algebras. Let formula_37 be a Coxeter group. The corresponding Iwahori-Hecke algebra formula_38 has the  standard basis formula_39, the group is partially ordered by the Bruhat order which is interval finite and has a dualization operation defined by formula_40. This is a precanonical structure on formula_38 that satisfies the sufficient condition above and the corresponding canonical basis of formula_38 is the Kazhdan–Lusztig basis with formula_44 being the Kazhdan–Lusztig polynomials. Linear algebra. If we are given an "n" × "n" matrix formula_2 and wish to find a matrix formula_46 in Jordan normal form, similar to formula_2, 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 formula_48 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 formula_2 possesses "n" linearly independent generalized eigenvectors. Generalized eigenvectors corresponding to distinct eigenvalues are linearly independent. If formula_50 is an eigenvalue of formula_2 of algebraic multiplicity formula_52, then formula_2 will have formula_52 linearly independent generalized eigenvectors corresponding to formula_50. For any given "n" × "n" matrix formula_2, 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 formula_2 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 formula_58 that are in the Jordan chain generated by formula_59 are also in the canonical basis. Computation. Let formula_60 be an eigenvalue  of formula_2 of algebraic multiplicity formula_62. First, find the ranks (matrix ranks) of the matrices formula_63. The integer formula_64 is determined to be the "first integer" for which formula_65 has rank formula_66 ("n" being the number of rows or columns of formula_2, that is, formula_2 is "n" × "n"). Now define The variable formula_70 designates the number of linearly independent generalized eigenvectors of rank "k" (generalized eigenvector rank; see generalized eigenvector) corresponding to the eigenvalue formula_60 that will appear in a canonical basis for formula_2. Note that 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 has eigenvalues formula_75 and formula_76 with algebraic multiplicities formula_77 and formula_78, but geometric multiplicities formula_79 and formula_80. For formula_81 we have formula_82 Therefore formula_87 Thus, a canonical basis for formula_2 will have, corresponding to formula_81 one generalized eigenvector each of ranks 4, 3, 2 and 1. For formula_94 we have formula_95 Therefore formula_98 Thus, a canonical basis for formula_2 will  have, corresponding to formula_94 one generalized eigenvector each of ranks 2 and 1. A canonical basis for formula_2 is formula_105 is the ordinary eigenvector associated with formula_106. formula_107 and formula_108 are generalized eigenvectors associated with formula_106. formula_110 is the ordinary eigenvector associated with formula_111. formula_112 is a generalized eigenvector associated with formula_111. A matrix formula_46 in Jordan normal form, similar to formula_2 is obtained as follows: where the matrix formula_118 is a generalized modal matrix for formula_2 and formula_120.