Unimodulär matris

I matematik är en unimodulär matris M en kvadratisk heltalsmatris med determinant +1 eller −1. På motsvarande sätt är det en heltalsmatris som är inverterbar över heltalen : det finns en heltalsmatris N som är dess inversa (dessa är ekvivalenta enligt Cramers regel ). Således har varje ekvation Mx = b , där M och b båda har heltalskomponenter och M är unimodulär, en heltalslösning. De n × n unimodulära matriserna bildar en grupp som kallas den n × n allmänna linjära gruppen över ${\displaystyle \mathbb {Z} } ,$ som betecknas $\operatorname {GL} _{n} (\mathbb {Z} )$ .

Exempel på unimodulära matriser

Unimodulära matriser bildar en undergrupp av den allmänna linjära gruppen under matrismultiplikation , dvs följande matriser är unimodulära:

Identitetsmatris
Inversen av en unimodulär matris
Produkten av två unimodulära matriser

Andra exempel inkluderar:

Pascal matriser
Permutationsmatriser
de tre transformationsmatriserna i det ternära trädet av primitiva Pythagoras trippel
Vissa transformationsmatriser för rotation , skjuvning (båda med determinant 1) och reflektion (determinant −1).
Den unimodulära matrisen som används (möjligen implicit) i gitterreduktion och i Hermites normala form av matriser.
Kronecker -produkten av två unimodulära matriser är också unimodulär. Detta följer eftersom $\det(A\otimes B)=(\det A)^{q}(\det B)^{p },$ där p och q är dimensionerna för A respektive B .

Total unimodularitet

En totalt unimodulär matris (TU-matris) är en matris för vilken varje kvadratisk icke-singulär submatris är unimodulär. På motsvarande sätt har varje kvadratisk submatris determinant 0, +1 eller −1. En helt unimodulär matris behöver inte vara kvadratisk själv. Av definitionen följer att varje submatris av en totalt unimodulär matris i sig själv är totalt unimodulär (TU). Dessutom följer att varje TU-matris endast har 0, +1 eller −1 poster. Det omvända är inte sant, dvs en matris med endast 0, +1 eller −1 poster är inte nödvändigtvis unimodulär. En matris är TU om och endast om dess transponering är TU.

Helt unimodulära matriser är extremt viktiga i polyedrisk kombinatorik och kombinatorisk optimering eftersom de ger ett snabbt sätt att verifiera att ett linjärt program är integral (har ett integraloptimum, när något optimum existerar). Specifikt, om A är TU och b är integral, då linjära program av former som $\{\min cx\mid Ax\geq b,x\geq 0\ }$ eller $\{\max cx\mid Ax\leq b\}$ har integraloptima, för alla c . Om A därför är helt unimodulär och b är integral, är varje ytterpunkt i den möjliga regionen (t.ex. ${\displaystyle \{x\mid Ax\geq b\}})$ integral och därmed den genomförbara regionen är en integrerad polyeder.

Vanliga helt unimodulära matriser

1. Den oorienterade incidensmatrisen för en tvådelad graf , som är koefficientmatrisen för tvådelad matchning , är helt unimodulär (TU). (Den oorienterade incidensmatrisen för en icke-tvådelad graf är inte TU.) Mer allmänt, i bilagan till en artikel av Heller och Tompkins, bevisar AJ Hoffman och D. Gale följande. Låt $A$ vara en m x n matris vars rader kan delas upp i två disjunkta uppsättningar $B$ och $C$ . Då räcker följande fyra villkor tillsammans för att A ska vara helt unimodulärt:

Varje post i $A$ är 0, +1 eller −1;
Varje kolumn i $A$ innehåller högst två poster som inte är noll (dvs +1 eller −1);
Om två poster som inte är noll i en kolumn av $A$ har samma tecken, så är raden av en i $B$ och den andra i $C$ ;
Om två poster som inte är noll i en kolumn av $A$ har motsatta tecken, är raderna för båda i ${\displaystyle B} ,$ eller båda i $C$ .

Det insågs senare att dessa villkor definierar en incidensmatris för en balanserad graf med tecken ; sålunda säger detta exempel att incidensmatrisen för en signerad graf är helt unimodulär om den signerade grafen är balanserad. Det omvända gäller för tecken med tecken utan halvkanter (detta generaliserar egenskapen hos den oorienterade incidensmatrisen för en graf).

2. Begränsningarna för maximalt flöde och minimala kostnadsflödesproblem ger en koefficientmatris med dessa egenskaper (och med tomt C ). Sådana nätverksflödesproblem med begränsade heltalskapaciteter har således ett integrerat optimalt värde. Observera att detta inte gäller för flervaruflödesproblem, där det är möjligt att ha bråkdelsoptimalt värde även med begränsade heltalskapaciteter.

3. Egenskapen ettor i följd: om A är (eller kan permuteras till) en 0-1-matris där ettorna visas i följd för varje rad, då är A TU. (Detsamma gäller för kolumner eftersom transponeringen av en TU-matris också är TU.)

4. Varje nätverksmatris är TU. Raderna i en nätverksmatris motsvarar ett träd T = ( V , R ) , vars bågar har en godtycklig orientering (det är inte nödvändigt att det finns en rotpunkt r så att trädet är "rotat i r " eller " out of r "). Kolumnerna motsvarar en annan uppsättning C av bågar på samma vertexuppsättning V . För att beräkna inmatningen på rad R och kolumn C = st , titta på s -to- t -vägen P i T ; då är posten:

+1 om båge R visas framåt i P ,
−1 om båge R visas baklänges i P ,
0 om båge R inte visas i P .

Se mer i Schrijver (2003).

5. Ghouila-Houri visade att en matris är TU iff för varje delmängd R av rader, det finns en tilldelning $s:R\to \pm 1$ av tecken till rader så att den signerade summan $\sum _{r\in R}s(r)r$ (som är en radvektor med samma bredd som matrisen) har alla sina poster i $\{0,\pm 1\}$ (dvs. rad-undermatrisen har högst en avvikelse ). Detta och flera andra om-och-bara-om-karakteriseringar bevisas i Schrijver (1998).

6. Hoffman och Kruskal bevisade följande teorem. Antag att $G$ är en riktad graf utan 2-dicycles, $P$ är mängden av alla dipather i $G$ och $A$ är 0-1 incidensmatrisen av $V(G)$ mot $P$ . Då $A$ helt unimodulär om och bara om varje enkel godtyckligt orienterad cykel i $G$ består av omväxlande framåt- och bakåtbågar.

7. Antag att en matris har 0-( $\pm$ 1) poster och i varje kolumn är posterna icke-minskande från topp till botten (så alla −1:or är överst, sedan 0:or, sedan 1:or är på botten). Fujishige visade att matrisen är TU iff varje 2-av-2 submatris har determinant i , $\displaystyle 0,\pm 1}$ .

8. Seymour (1980) visade en fullständig karakterisering av alla TU-matriser, som vi beskriver här endast informellt. Seymours teorem är att en matris är TU om och bara om den är en viss naturlig kombination av några nätverksmatriser och några kopior av en viss 5-av-5 TU-matris.

Konkreta exempel

1. Följande matris är helt unimodulär:

A=\left[{\begin{array}{rrrrrr}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\ end{array}}\right].

Denna matris uppstår som koefficientmatrisen för begränsningarna i den linjära programmeringsformuleringen av det maximala flödesproblemet på följande nätverk:

2. Valfri matris av formen

A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb & +1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].

är inte helt unimodulär, eftersom den har en kvadratisk submatris med determinanten −2.

Abstrakt linjär algebra

Abstrakt linjär algebra beaktar matriser med poster från valfri kommutativ ring ${\displaystyle R} ,$ inte begränsad till heltal. I detta sammanhang är en unimodulär matris en som är inverterbar över ringen; motsvarande, vars determinant är en enhet . Denna grupp betecknas $\operatörsnamn {GL} _{n}(R)$ . En rektangulär $k$ -by- $m$ matris sägs vara unimodulär om den kan utökas med $mk$ rader i $R^{m}$ till en unimodulär kvadratisk matris.

Över ett fält har unimodulär samma betydelse som icke -singular . Unimodulär avser här matriser med koefficienter i någon ring (ofta heltal) som är inverterbara över den ringen, och man använder icke-singular för att betyda matriser som är inverterbara över fältet.

Se även

Anteckningar

^ Termen myntades av Claude Berge , se Hoffman , AJ; Kruskal , J. (2010), "Introduktion till Integral Boundary Points of Convex Polyhedra ", i M. Jünger; et al. (red.), 50 Years of Integer Programming, 1958-2008 , Springer-Verlag, s. 49–50
^ Heller, I.; Tompkins, CBGh (1956), "An Extension of a Theorem of Dantzig's", i Kuhn , HW; Tucker , AW (red.), Linear Inequalities and Related Systems , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, s. 247–254
^ T. Zaslavsky (1982), "Signerade grafer," Discrete Applied Mathematics 4, s. 401–406.
^ Fulkerson, DR; Gross, OA (1965). "Incidensmatriser och intervallgrafer" . Pacific Journal of Mathematics . 15 (3): 835–855. ISSN 0030-8730 .
^ Hoffman, AJ; Kruskal , JB (1956), "Integral Boundary Points of Convex Polyhedra", i Kuhn , HW; Tucker , AW (red.), Linear Inequalities and Related Systems , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, s. 223–246
^ Fujishige, Satoru (1984), "A System of Linear inequalities with a Submodular Function on (0, ±1) Vectors", Linjär algebra och dess tillämpningar, 63 : 253–266, doi : 10.1016/0024-3795(84) 90147-2
^ Seymour , PD (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Series B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1
^ Lang, Serge (2002). Algebra (rev. 3:e uppl.). Springer. sid. 510, avsnitt XIII.3. ISBN 0-387-95385-X .
^ Rosenthal, J.; Maze, G.; Wagner, U. (2011), Natural Density of Rectangular Unimodular Integer Matrices , Linjär algebra och dess tillämpningar, vol. 434, Elsevier, s. 1319–1324
^ Micheli, G.; Schnyder, R. (2016), Densiteten av unimodulära matriser över integrerat slutna underringar av funktionsfält , Contemporary Developments in Finite Fields and Applications, World Scientific, s. 244–253
^ Guo, X.; Yang, G. (2013), Sannolikheten för rektangulära unimodulära matriser över Fq [x] , Linjär algebra och dess tillämpningar, Elsevier, s. 2675–2682

Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Avsnitt 13.2", Combinatorial Optimization: Algorithms and Complexity , Mineola, NY: Dover Publications, sid. 316, ISBN 978-0-486-40258-1
Alexander Schrijver (1998), teori om linjär- och heltalsprogrammering . John Wiley & Sons, ISBN 0-471-98232-6 (matematisk)
Alexander Schrijver (2003), Combinatorial Optimization: Polyhedra and Efficiency , Springer

externa länkar

[1] Termen myntades av Claude Berge , se Hoffman , AJ; Kruskal , J. (2010), "Introduktion till Integral Boundary Points of Convex Polyhedra ", i M. Jünger; et al. (red.), 50 Years of Integer Programming, 1958-2008 , Springer-Verlag, s. 49–50

[2] Heller, I.; Tompkins, CBGh (1956), "An Extension of a Theorem of Dantzig's", i Kuhn , HW; Tucker , AW (red.), Linear Inequalities and Related Systems , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, s. 247–254

[3] T. Zaslavsky (1982), "Signerade grafer," Discrete Applied Mathematics 4, s. 401–406.

[4] Fulkerson, DR; Gross, OA (1965). "Incidensmatriser och intervallgrafer" . Pacific Journal of Mathematics . 15 (3): 835–855. ISSN 0030-8730 .

[5] Hoffman, AJ; Kruskal , JB (1956), "Integral Boundary Points of Convex Polyhedra", i Kuhn , HW; Tucker , AW (red.), Linear Inequalities and Related Systems , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, s. 223–246

[6] Fujishige, Satoru (1984), "A System of Linear inequalities with a Submodular Function on (0, ±1) Vectors", Linjär algebra och dess tillämpningar, 63 : 253–266, doi : 10.1016/0024-3795(84) 90147-2

[7] Seymour , PD (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Series B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1

[8] Lang, Serge (2002). Algebra (rev. 3:e uppl.). Springer. sid. 510, avsnitt XIII.3. ISBN 0-387-95385-X .

[9] Rosenthal, J.; Maze, G.; Wagner, U. (2011), Natural Density of Rectangular Unimodular Integer Matrices , Linjär algebra och dess tillämpningar, vol. 434, Elsevier, s. 1319–1324

[10] Micheli, G.; Schnyder, R. (2016), Densiteten av unimodulära matriser över integrerat slutna underringar av funktionsfält , Contemporary Developments in Finite Fields and Applications, World Scientific, s. 244–253

[11] Guo, X.; Yang, G. (2013), Sannolikheten för rektangulära unimodulära matriser över Fq [x] , Linjär algebra och dess tillämpningar, Elsevier, s. 2675–2682

Matrisklasser _
Explicit begränsade poster	Alternant Antidiagonal Anti-Hermitian Antisymmetrisk Pilspets Band Bidiagonal Bisymmetrisk Block-diagonal Blockera Block tridiagonal Boolean Cauchy Centrosymmetrisk Konferens Komplexa Hadamard Kopositiv Diagonalt dominant Diagonal Diskret Fourier Transform Elementärt Likvärdig Frobenius Generaliserad permutation Hadamard Hankel Hermitian Hessenberg Ihålig Heltal Logisk Matrisenhet Metzler Moore Icke negativ Pentadiagonal Permutation Persymmetrisk Polynom Kvaternionisk Signatur Skew-Hermitian Skevsymmetrisk Horisont Gles Sylvester Symmetrisk Toeplitz Triangulär Tridiagonal Vandermonde Walsh Z
Konstant	Utbyta Hilbert Identitet Lehmer Av ettor Pascal Pauli Redheffer Flytta Noll
Villkor för egenvärden eller egenvektorer	Följeslagare Konvergerande Defekt Bestämd Diagonaliserbar Hurwitz Positivt-definitivt Stieltjes
Tillfredsställande villkor på produkter eller inverser	Kongruent Idempotent eller projektion Inverterbar Ofrivilligt Nilpotent Vanligt Ortogonal Unimodulär Unipotent Enhetlig Helt unimodulärt Vägning
Med specifika applikationer	Justera Växlande tecken Förändrad Bézout Carleman Cartan Cirkulerande Kofaktor Kommutering Förvirring Coxeter Distans Duplicering och eliminering Euklidiskt avstånd Fundamental (linjär differentialekvation) Generator Gram Hessian Hushållare Jacobian Ögonblick Löna sig Plocka Slumpmässig Rotation Seifert Klippa Likhet Symplektisk Helt positivt Omvandling
Används i statistik	Centrering Korrelation Kovarians Design Dubbelstokastisk Fisher information Hatt Precision Stokastisk Övergång
Används i grafteori	Närhet Biadjacency Grad Edmonds Frekvens Laplacian Seidel angränsning Tutte
Används inom naturvetenskap och teknik	Cabibbo–Kobayashi–Maskawa Densitet Grundläggande (datorseende) Lugnt associativt Gamma Gell-Mann Hamiltonian Oregelbunden Överlappning S Statsövergång Utbyte Z (kemi)
Relaterade termer	Jordan normal form Linjärt oberoende Matris exponentiell Matrisrepresentation av koniska sektioner Perfekt matris Pseudoinvers Rad echelon form Wronskian
Matematikportal Lista över matriser Kategori:Matriser