Alternating sign matrix: Difference between revisions

Revision as of 19:23, 9 April 2012

Latest revision as of 07:02, 17 June 2025

(45 intermediate revisions by 32 users not shown)

Line 1:

{{distinguish|Alternant matrix}}

{{Image frame|width=340|align=right|caption=The seven alternating sign matrices of size 3

|content=<math>\begin{matrix}

\begin{bmatrix}

1 & 0 & 0\\

0 & 1 & 0\\

0 & 0 & 1

\end{bmatrix}

\qquad

\begin{bmatrix}

1 & 0 & 0\\

0 & 0 & 1\\

0 & 1 & 0

\end{bmatrix}

\\

\begin{bmatrix}

0 & 1 & 0\\

1 & 0 & 0\\

0 & 0 & 1

\end{bmatrix}

\qquad

\begin{bmatrix}

0 & 1 & 0\\

1 & -1 & 1\\

0 & 1 & 0

\end{bmatrix}

\qquad

\begin{bmatrix}

0 & 1 & 0\\

0 & 0 & 1\\

1 & 0 & 0

\end{bmatrix}

\\

\begin{bmatrix}

0 & 0 & 1\\

1 & 0 & 0\\

0 & 1 & 0

\end{bmatrix}

\qquad

\begin{bmatrix}

0 & 0 & 1\\

0 & 1 & 0\\

1 & 0 & 0

\end{bmatrix}

\end{matrix}</math>}}

In [[mathematics]], an '''alternating sign matrix''' is a [[square matrix]] of 0s, 1s, and &minus;1s−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.

==Examples==

In [[mathematics]], an '''alternating sign matrix''' is a square matrix of 0s, 1s, and &minus;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 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.

For example, theA [[permutation matricesmatrix]] areis an alternating sign matricesmatrix, asand an alternating sign matrix is a permutation matrix if and only if no entry equals {{math|−1}}.

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

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

:<math>

\begin{bmatrix}

Line 14 ⟶ 71:

</math>

==Alternating sign matrix theorem==
The ''alternating sign matrix conjecturetheorem'' states that the number of <math>n\times n</math> alternating sign matrices is

:<math>

\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} = \frac{1!\, 4! \,7! \cdots (3n-2)!}{n!\, (n+1)! \cdots (2n-1)!}.

</math>

The first few terms in this sequence for ''n'' = 0, 1, 2, 3, … are

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

This conjecturetheorem 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://arxiv.org/abs/math.CO/9712207 "Another proof of the alternating sign matrix conjecture"], ''International Mathematics Research Notes'' (1996), 139-150.</ref> based on the [[Yang-BaxterYang–Baxter equation]] for the six -vertex model with ___domain -wall boundary conditions, that uses a [http://www.mendeley.com/c/29813067/determinant calculation due to Anatoli Izergin-1992-.<ref>"Determinant- formula- for- the- six-vertex- model/", determinant]A. G. Izergin dueet toal. Anatoli1992 Izergin,''J. whichPhys. solvesA'': [http://projecteuclidMath.org/DPubS?service=UI&version=1 Gen.0&verb=Display&handle=euclid 25 4315.cmp</1103921777ref> recurrenceIn relations]2005, duea tothird proof was given by [[VladimirIlse KorepinFischer]] 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 conjectureproblem==

In 2001, A. Razumov and Y. Stroganov conjectured a connection between O(1) loop model, fully packagedpacked loop model (FPL) and ASMs.<ref>Razumov, A.V., Stroganov Yu.G., [https://arxiv.org/abs/cond-mat/0012141 Spin chains and combinatorics], ''Journal of Physics A'', '''34''' (2001), 3185-3190.</ref>

This conjecture was proved in 2010 by Cantini and Sportiello.<ref>L. Cantini and A. Sportiello, [https://arxiv.org/abs/1003.3376 Proof of the Razumov-Stroganov conjecture]''Journal of Combinatorial Theory, Series A'', '''118 (5)''', (2011) 1549–1574,</ref>

==References and further reading==

{{reflist}}

* [[David Bressoud|Bressoud, David M.]], ''Proofs and Confirmations'', MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.

* [[David Bressoud|Bressoud, David M.]] and Propp, James, [http://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.

==Further reading==

* [[Greg Kuperberg|Kuperberg, Greg]], [http://front.math.ucdavis.edu/math.CO/9712207 Another proof of the alternating sign matrix conjecture], ''International Mathematics Research Notes'' (1996), 139-150.

* [[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}}

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

* [[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-646637–646.

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

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

* Razumov, A.V., Stroganov Yu.G., [http://arxiv.org/abs/cond-mat/0012141 Spin chains and combinatorics], ''Journal of Physics A'', '''34''' (2001), 3185-3190.

* 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-359340–359.

* Razumov, A.V., Stroganov Yu.G., [http://arxiv.org/abs/math/0104216 Combinatorial nature of ground state vector of O(1) loop model], ''Theor. Math. Phys.'', '''138''' (2004), 333-337.

* RazumovPropp, A.V., Stroganov Yu.G.James, [httphttps://arxiv.org/abs/cond-matmath/01081030208125v1 O(1)The loopmany model with different boundary conditions and symmetry classesfaces of alternating-sign matrices], ''Theor.Discrete Math.Mathematics Phys.and Theoretical Computer Science'', Special issue on '''142'Discrete Models: Combinatorics, Computation, and Geometry'' (2005July 2001), 237-243.

* Razumov, A. V., Stroganov Yu. G., [httphttps://arxiv.org/abs/cond-matmath/00121410104216 SpinCombinatorial chainsnature andof combinatoricsground state vector of O(1) loop model], ''JournalTheor. ofMath. Physics APhys.'', '''34138''' (20012004), 3185-3190333–337.

* Robbins, David P., The story of <math>1, 2, 7, 42, 429, 7436, \cdots</math>, ''The Mathematical Intelligencer'', 13 (2), 12-19 (1991).

* Razumov, A. V., Stroganov Yu. G., O(1) loop model with different boundary conditions and symmetry classes of alternating-sign matrices], ''Theor. Math. Phys.'', '''142''' (2005), 237–243, {{arxiv|cond-mat/0108103}}

* 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.

* [[David P. Robbins|Robbins, David P.]], The story of <math>1, 2, 7, 42, 429, 7436, \cdotsdots</math>, ''The Mathematical Intelligencer'', 13 (2), 12-1912–19 (1991), {{doi|10.1007/BF03024081}}.

* Zeilberger, Doron, [http://nyjm.albany.edu:8000/j/1996/2-4.pdf Proof of the refined alternating sign matrix conjecture], ''New York Journal of Mathematics'' 2 (1996), 59-68.

* [[Doron Zeilberger|Zeilberger, Doron]], [http://wwwnyjm.combinatoricsalbany.orgedu:8000/Volume_3j/Abstracts1996/v3i2r132-4.htmlpdf Proof of the refined alternating sign matrix conjecture], ''[http://www.combinatorics.org/New ElectronicYork Journal of Combinatorics]Mathematics'' 32 (1996), R1359–68.

==External links==

* [http://mathworld.wolfram.com/AlternatingSignMatrix.html Alternating sign matrix] entry in [[MathWorld]]

* [http://www.findstat.org/AlternatingSignMatrices Alternating sign matrices] entry in the [http://www.findstat.org/ FindStat] database

{{Matrix classes}}

[[Category:Matrices]]

[[Category:Enumerative combinatorics]]

[[Category:Matrices (mathematics)]]

[[eo:Alterna signa matrico]]

[[Category:Enumerative combinatorics]]

[[sl:Matrika s spremenljivimi predznaki]]

[[th:เมทริกซ์เครื่องหมายสลับ]]