en>Ivan Štambuk: /* Parameterized complexity */

2014-01-24T07:06:44Z

Parameterized complexity

New page

In mathematics, the '''quasideterminant''' is a replacement for the [[determinant]] for [[Matrix (mathematics)|matrices]] with noncommutative entries. Example 2 × 2 quasideterminants are as follows:

: <math>
\left|\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22} \end{array}
\right|_{11} = a_{11} - a_{12}{a_{22}}^{-1}a_{21}
\qquad
\left|\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22} \end{array}
\right|_{12} = a_{12} - a_{11}{a_{21}}^{-1}a_{22}.
</math>

In general, there are ''n''<sup>2</sup> quasideterminants defined for an ''n'' × ''n'' matrix (one for each position in the matrix), but the presence of the inverted terms above should give the reader pause: they are not always defined, and even when they are defined, they do not reduce to determinants when the entries commute. Rather,

: <math>
\left|A\right|_{ij} = (-1)^{i+j} \frac{\det A}{\det A^{ij}} ,
</math>
where <math>A^{ij}</math> means delete the ''i''th row and ''j''th column from ''A''.

The <math>2\times2</math> examples above were introduced between 1926 and 1928 by [[Archibald Read Richardson|Richardson]]
<ref name="Ric1">A.R. Richardson, Hypercomplex determinants, ''Messenger of Math.'' 55 (1926), no. 1.</ref>
<ref name="Ric2">A.R. Richardson, Simultaneous linear equations over a division algebra, ''Proc. London Math. Soc.'' 28 (1928), no. 2.</ref> and Heyting,
<ref name="Hey">A. Heyting, Die theorie der linearen gleichungen in einer zahlenspezies mit nichtkommutativer multiplikation, ''Math. Ann. 98'' (1928), no. 1.</ref>
but they were marginalized at the time because they were not polynomials in the entries of <math>A</math>. These examples were rediscovered and given new life in 1991 by [[Israel Gelfand|I.M. Gelfand]] and V.S. Retakh.
<ref name="GelRet1">I. Gelfand, V. Retakh, Determinants of matrices over noncommutative rings, ''Funct. Anal. Appl.'' 25 (1991), no. 2.</ref>
<ref name="GelRet2">I. Gelfand, V. Retakh, Theory of noncommutative determinants, and characteristic functions of graphs, ''Funct. Anal. Appl.'' 26 (1992), no. 4.</ref>
There, they develop quasideterminantal versions of many familiar determinantal properties. For example, if <math>B</math> is built from <math>A</math> by rescaling its <math>i</math>-th row (on the left) by <math>\left.\rho\right.</math>, then <math>\left|B\right|_{ij} = \rho \left|A\right|_{ij}</math>.
Similarly, if <math>B</math> is built from <math>A</math> by adding a (left) multiple of the <math>k</math>-th row to another row, then <math>\left|B\right|_{ij} = \left|A\right|_{ij} \,\, (\forall j; \forall k\neq i)</math>. They even develop a quasideterminantal
version of [[Cramer's rule]].

==Definition==
[[Image:QuasidetPictureDef.gif|200px|thumb|(a picture definition)]]
Let <math>A</math> be an <math>n\times n</math> matrix over a (not necessarily commutative)
ring <math>R</math> and fix <math>1\leq i,j\leq n</math>. Let <math>a_{ij}</math>
denote the (<math>i,j</math>)-entry of <math>A</math>, let <math>r_i^j</math> denote the <math>i</math>-th row of <math>A</math> with column <math>j</math> deleted, and let <math>c_j^i</math> denote the <math>j</math>-th column of <math>A</math> with row <math>i</math> deleted. The (<math>i,j</math>)-quasideterminant of <math>A</math> is defined if the submatrix <math>A^{ij}</math> is invertible over <math>R</math>. In this case,
::<math>
\left|A\right|_{ij} = a_{ij} - r_i^j\, \bigl(A^{ij}\bigr)^{-1}\, c_j^i .
</math>
Recall the formula (for commutative rings) relating <math>A^{-1}</math> to the determinant, namely <math>(A^{-1})_{ji} = (-1)^{i+j} \frac{\det A^{ij}}{\det A}</math>. The above definition is a generalization in that (even for noncommutative rings) one has
::<math>
\bigl(A^{-1}\bigr)_{\!ji} = \left|A\right|_{ij}^{\,-1}
</math>
whenever the two sides makes sense.

==Identities==
One of the most important properties of the quasideterminant is what Gelfand and Retakh
call the “heredity principle.” It allows one to take a quasideterminant in
stages (and has no commutative counterpart). To illustrate, suppose
::<math>
\left(\begin{array}{cc}
A_{11} & A_{12} \\
A_{21} & A_{22} \end{array}
\right)
</math>
is a [[block matrix]] decomposition of an <math>n\times n</math> matrix <math>A</math> with
<math>A_{11}</math> a <math>k \times k</math> matrix. If the (<math>i,j</math>)-entry of <math>A</math> lies within <math>A_{11}</math>, it says that
:<math>
\left|A\right|_{ij} = \left|A_{11} - A_{12}\,{A_{22}}^{-1}\,A_{21}\right|_{ij}.
</math>
That is, the quasideterminant of a quasideterminant is a quasideterminant! To put it less succinctly: UNLIKE determinants, quasideterminants treat matrices with block-matrix entries no differently than ordinary matrices (something determinants cannot do since block-matrices generally don't commute with one another). That is, while the precise form of the above identity is quite surprising, the existence of ''some'' such identity is less so.
Other identities from the papers <ref name="GelRet1"/><ref name="GelRet2"/> are (i) the so-called “homological relations,” stating that two quasideterminants in a common row or column are closely related to one another, and (ii) the [[James Joseph Sylvester|Sylvester]] formula.

(i) Two quasideterminants sharing a common row or column satisfy
::<math>
\left|A\right|_{ij} |A^{il}|_{kj}^{\,-1} = - \left|A\right|_{il} |A^{ij}|_{kl}^{\,-1}
</math>
or
::<math>
|A^{kj}|_{il}^{\,-1} \left|A\right|_{ij} = - |A^{ij}|_{kl}^{\,-1} \left|A\right|_{kj} ,
</math>
respectively, for all choices <math>i\neq k</math>, <math>j\neq l</math> so that the
quasideterminants involved are defined.

(ii) Like the heredity principle, the Sylvester identity is a way to recursively
compute a quasideterminant. To ease notation, we display a special case. Let
<math>A_0</math> be the upper-left <math>k \times k</math> submatrix of an
<math>n \times n</math> matrix <math>A</math> and fix a coordinate (<math>i,j</math>) in
<math>A_0</math>. Let <math>B=(b_{pq})</math> be the <math>(n-k)\times(n-k)</math> matrix, with <math>b_{pq}</math> defined as the (<math>p,q</math>)-quasideterminant of the <math>(k+1)\times(k+1)</math> matrix formed by adjoining to <math>A_0</math> the first <math>k</math> columns of row <math>p</math>, the first <math>k</math> rows of column <math>q</math>, and the entry <math>a</math><sub><math>pq</math></sub>. Then one has
::<math>
\left|B\right|_{ij} = \left|A\right|_{ij} .
</math>

Many more identities have appeared since the first articles of Gelfand and Retakh on the subject, most of them being analogs of classical determinantal identities. An important source is Krob and Leclerc's 1995 article,
<ref name="KroLec">D. Krob, B. Leclerc, Minor identities for quasi-determinants and quantum determinants, ''Comm. Math. Phys.'' 169 (1995), no. 1.</ref> To highlight one, we consider the row/column expansion identities. Fix a row <math>i</math> to expand along. Recall the determinantal formula
<math> \det A = \sum_l (-1)^{i+l} a_{il} \cdot \det A^{il}</math>.
Well, it happens that quasideterminants satisfy
::<math>
\left|A\right|_{ij} = a_{ij} - \sum_{l\neq j} a_{il}\cdot |A^{ij}|_{kl}^{\,-1} |A^{il}|_{kj}
</math>
(expansion along column <math>j</math>), and
::<math>
\left|A\right|_{ij} = a_{ij} - \sum_{k\neq i} |A^{kj}|_{il} |A^{ij}|_{kl}^{\,-1} \cdot a_{kj}
</math>
(expansion along row <math>i</math>).

==Connections to other determinants==
The quasideterminant is certainly not the only existing determinant analog for noncommutative settings—perhaps the most famous examples are the [[Dieudonné determinant]] and [[Quantum group|quantum]] determinant. However, these are related to the quasideterminant in some way. For example,
::<math>
{\det}_q A = \bigl|A\bigr|_{11}\,\left|A^{11}\right|_{22}\,\left|A^{12,12}\right|_{33} \,\cdots\,|a_{nn}|_{nn} ,
</math>
with the factors on the right-hand side commuting with each other. Other famous examples, such as [[Berezinian]]s, [[Moore determinant over a division algebra|Moore]] and Study determinants, [[Capelli's identity|Capelli determinants]], and Cartier-Foata-type determinants are also expressible in terms of quasideterminants. Gelfand has been known to define a (noncommutative) determinant as “good” if it may be expressed as products of quasiminors.

==Applications==
Paraphrasing their 2005 survey article with S. Gelfand and R. Wilson
,<ref name="GelGelRetWil">I. Gelfand, S. Gelfand, V. Retakh, R.L. Wilson, Quasideterminants. ''Adv. Math.'' 193 (2005), no. 1. ([http://arxiv.org/abs/math/0208146 eprint])</ref>
Gelfand and Retakh advocate for the adoption of
quasideterminants as “a main organizing tool in noncommutative algebra, giving
them the same role determinants play in commutative algebra.” By now,
substantive use has been made of the quasideterminant in such fields of mathematics as
integrable systems,
<ref name="EtiGelRet">P. Etingof, I. Gelfand, V. Retakh, Nonabelian integrable systems, quasideterminants, and Marchenko lemma. ''Math. Res. Lett. 5'' (1998), no. 1-2.</ref>
<ref name="GilNimSoo">C.R. Gilson, J.J.C. Nimmo, C.M. Sooman, On a direct approach to quasideterminant solutions of a noncommutative modified KP equation, ''J. Phys. A: Math. Theor.'' 41 (2008), no. 8. ([http://arxiv.org/abs/0711.3733 eprint])</ref>
representation theory,
<ref name="Mol">A. Molev, Yangians and their applications, in ''Handbook of algebra, Vol. 3,'' North-Holland, Amsterdam, 2003. ([http://arxiv.org/abs/math/0211288 eprint])</ref>
<ref name="BruKle">J. Brundan, A. Kleshchev, Parabolic presentations of the Yangian Y(gl_n), ''Comm. Math. Phys. 254'' (2005). ([http://arxiv.org/abs/math/0407011 eprint])</ref>
algebraic combinatorics,
<ref name="KonPak">M. Konvalinka, I. Pak, Non-commutative extensions of the MacMahon Master Theorem, ''Adv. Math.'' 216 (2007), no. 1. ([http://arxiv.org/abs/math/0607737 eprint])</ref>
the theory of ''noncommutative symmetric functions,''
<ref name="GelKroLLRT">I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, J.-Y. Thibon, Noncommutative symmetric functions. ''Adv. Math.'' 112 (1995), no. 2. ([http://arxiv.org/abs/hep-th/9407124 eprint])</ref>
the theory of ''polynomials over division rings,''
<ref name="GelRet3">I. Gelfand, V. Retakh, Noncommutative Vieta theorem and symmetric functions. ''The Gelfand Mathematical Seminars, 1993--1995.''</ref>
and noncommutative geometry.
<ref name="Sko">Z. Škoda, Noncommutative localization in noncommutative geometry, in “Non-commutative localization in algebra and topology”, ''London Math. Soc. Lecture Note Ser., 330,'' Cambridge Univ. Press, Cambridge, 2006.
([http://arxiv.org/abs/math/0403276 eprint])</ref>
<ref name="Lau">A. Lauve, Quantum and quasi-Plücker coordinates, ''J. Algebra'' (296) 2006, no. 2. ([http://arxiv.org/abs/math/0406062 eprint])</ref>
<ref name="BerRet">A. Berenstein, V. Retakh, Noncommutative double Bruhat cells and their factorizations, ''IMRN'' 2005. ([http://arxiv.org/abs/math/0407010 eprint])</ref>

Several of the applications above make use of ''quasi-Plücker coordinates,'' which parametrize noncommutative Grassmannians and flags in much the same way as [[Plücker embedding|Plücker coordinates]] do [[Grassmannians]] and flags over commutative fields. More information on these can be found in the survey article.<ref name="GelGelRetWil"/>

== See also ==
* [[MacMahon Master theorem]]

==References==
{{reflist}}

[[Category:Matrix theory]]
[[Category:Determinants]]

Longest path problem - Revision history

en>Ivan Štambuk: /* Parameterized complexity */