Alternating sign matrix: Difference between revisions

Revision as of 09:27, 20 April 2021

Latest revision as of 07:02, 17 June 2025

(11 intermediate revisions by 9 users not shown)

Line 44:

\end{bmatrix}

\end{matrix}</math>}}

In [[mathematics]], an '''alternating sign matrix''' is a [[square matrix]] of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices generalize [[Permutation matrix|permutation matrices]] and arise naturally when using [[Dodgson condensation]] to compute a determinant. They are also closely related to the [[six-vertex model]] with ___domain wall boundary conditions from [[statistical mechanics]]. They were first defined by William Mills, [[David P. Robbins|David Robbins]], and Howard Rumsey in the former context.<ref>{{citation

| last = Hone | first = Andrew N. W.

| doi = 10.1098/rsta.2006.1887

| issue = 1849

| journal = Philosophical Transactions of the Royal Society of London

| mr = 2317901

| pages = 3183–3198

| title = Dodgson condensation, alternating signs and square ice

| volume = 364

| year = 2006| bibcode = 2006RSPTA.364.3183H

}}</ref> They are also closely related to the [[six-vertex model]] with ___domain wall boundary conditions from [[statistical mechanics]]. They were first defined by William Mills, [[David P. Robbins|David Robbins]], and Howard Rumsey in the former context.

==ExampleExamples==

An example of an alternating sign matrix (that is not also a permutation matrix) is

A [[permutation matrix]] is an alternating sign matrix, and an alternating sign matrix is a permutation matrix if and only if no entry equals {{math|−1}}.

[[File:Matrice signes alternants 4x4.svg|thumbnail|Puzzle picture]]

An example of an alternating sign matrix (that is not also a permutation matrix) is

[[File:Matrice signes alternants 4x4.svg|thumbnail|Puzzle picture]]

:<math>

\begin{bmatrix}

Line 68 ⟶ 79:

:1, 1, 2, 7, 42, 429, 7436, 218348, … {{OEIS|id=A005130}}.

This theorem was first proved by [[Doron Zeilberger]] in 1992.<ref>Zeilberger, Doron, [http://www.combinatorics.org/Volume_3/Abstracts/v3i2r13.html "Proof of the alternating sign matrix conjecture"], ''[http://www.combinatorics.org/ Electronic Journal of Combinatorics]'' 3 (1996), R13.</ref> In 1995, [[Greg Kuperberg]] gave a short proof<ref>[[Greg Kuperberg|Kuperberg, Greg]], [http://frontarxiv.math.ucdavis.eduorg/abs/math.CO/9712207 "Another proof of the alternating sign matrix conjecture"], ''International Mathematics Research Notes'' (1996), 139-150.</ref> based on the [[Yang–Baxter equation]] for the six-vertex model with ___domain-wall boundary conditions, that uses a determinant calculation due to Anatoli Izergin.<ref>"Determinant formula for the six-vertex model", A. G. Izergin et al. 1992 ''J. Phys. A'': Math. Gen. 25 4315.</ref> AIn 2005, a third proof was given by [[Ilse Fischer]] using what is called the ''operator method''.<ref>{{Cite journal|last=Fischer|first=Ilse|title=A new proof of the refined alternating sign matrix theorem|journal=Journal of Combinatorial Theory, Series A|year=2005|volume=114|issue=2|pages=253–264|doi=10.1016/j.jcta.2006.04.004|arxiv=math/0507270|bibcode=2005math......7270F}}</ref>

==Razumov–Stroganov problem==

Line 79 ⟶ 90:

==Further reading==

* [[David Bressoud|Bressoud, David M.]], ''Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture'', MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.{{ISBN|978-0521666466}}

* [[David Bressoud|Bressoud, David M.]] and Propp, James, [httphttps://www.ams.org/notices/199906/fea-bressoud.pdf How the alternating sign matrix conjecture was solved], ''Notices of the American Mathematical Society'', 46 (1999), 637–646.

* Mills, William H., [[David P. Robbins|Robbins, David P.]], and Rumsey, Howard Jr., Proof of the Macdonald conjecture, ''Inventiones Mathematicae'', 66 (1982), 73–87.

* Mills, William H., [[David P. Robbins|Robbins, David P.]], and Rumsey, Howard Jr., Alternating sign matrices and descending plane partitions, ''Journal of Combinatorial Theory, Series A'', 34 (1983), 340–359.

Line 95 ⟶ 106:

{{Matrix classes}}

[[Category:Matrices (mathematics)]]

[[Category:Enumerative combinatorics]]