3311:
1641:
406:
is unimodular. Equivalently, every square submatrix has determinant 0, +1 or −1. A totally unimodular matrix need not be square itself. From the definition it follows that any submatrix of a totally unimodular matrix is itself totally unimodular (TU). Furthermore it follows that any TU matrix
895:; thus, this example says that the incidence matrix of a signed graph is totally unimodular if the signed graph is balanced. The converse is valid for signed graphs without half edges (this generalizes the property of the unoriented incidence matrix of a graph).
1375:
1) entries and in each column, the entries are non-decreasing from top to bottom (so all −1s are on top, then 0s, then 1s are on the bottom). Fujishige showed that the matrix is TU iff every 2-by-2 submatrix has determinant in
635:, is totally unimodular (TU). (The unoriented incidence matrix of a non-bipartite graph is not TU.) More generally, in the appendix to a paper by Heller and Tompkins, A.J. Hoffman and D. Gale prove the following. Let
368:
1412:(1980) proved a full characterization of all TU matrices, which we describe here only informally. Seymour's theorem is that a matrix is TU if and only if it is a certain natural combination of some
506:
195:
560:
1884:
1127:
613:
1079:
154:
1162:
2969:
1793:
1627:
1403:
1977:
1373:
1290:
1950:
1924:
1904:
1837:
1350:
1330:
1310:
1261:
1241:
1217:
1193:
885:
865:
845:
822:
802:
782:
759:
736:
704:
684:
653:
3183:
2402:
1839:, not limited to the integers. In this context, a unimodular matrix is one that is invertible over the ring; equivalently, whose determinant is a
3274:
2320:
256:
3193:
2959:
707:
914:). Thus, such network flow problems with bounded integer capacities have an integral optimal value. Note that this does not apply to
2340:
2245:
411:
is not true, i.e., a matrix with only 0, +1 or −1 entries is not necessarily unimodular. A matrix is TU if and only if its
294:
2994:
2210:
2000:
here refers to matrices with coefficients in some ring (often the integers) which are invertible over that ring, and one uses
445:
2541:
159:
2758:
2395:
2205:
2057:
1409:
915:
40:
2833:
511:
2989:
2511:
1165:
423:
3093:
2964:
2878:
1850:
3198:
3088:
2796:
2476:
1633:
899:
419:
2365:
1632:
This matrix arises as the coefficient matrix of the constraints in the linear programming formulation of the
3233:
3162:
3044:
2904:
2501:
2388:
632:
2177:
Fujishige, Satoru (1984), "A System of Linear inequalities with a
Submodular Function on (0, ±1) Vectors",
2166:, Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, pp. 223–246
2095:, Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, pp. 247–254
3103:
2686:
2491:
2028:
1084:
3049:
2786:
2636:
2631:
2466:
2441:
2436:
1445:
577:
234:
214:
3310:
1667:
1640:
1168:
at most one). This and several other if-and-only-if characterizations are proven in
Schrijver (1998).
951:, each of whose arcs has an arbitrary orientation (it is not necessary that there exist a root vertex
3243:
2601:
2431:
2411:
2023:
210:
131:
925:
is (or can be permuted into) a 0-1 matrix in which for every row, the 1s appear consecutively, then
3264:
3238:
2816:
2621:
2611:
2347:
2328:
2033:
1983:
1844:
281:
120:
1049:
137:
3315:
3269:
3259:
3213:
3208:
3137:
3073:
2939:
2676:
2671:
2606:
2596:
2461:
2280:, Contemporary Developments in Finite Fields and Applications, World Scientific, pp. 244–253
1840:
1817:
1132:
918:, in which it is possible to have fractional optimal value even with bounded integer capacities.
616:
431:
250:
3347:
3326:
3113:
3108:
3098:
3078:
3039:
3034:
2858:
2843:
2838:
2829:
2824:
2771:
2666:
2616:
2561:
2531:
2526:
2506:
2496:
2456:
2336:
2316:
2310:
2241:
2132:
1992:
1652:
1430:
907:
400:
288:
277:
270:
74:
36:
1379:
3321:
3289:
3218:
3157:
3152:
3132:
3068:
2974:
2944:
2929:
2914:
2909:
2848:
2801:
2776:
2766:
2737:
2656:
2651:
2626:
2556:
2536:
2446:
2426:
2219:
2186:
2159:
2088:
1810:
408:
86:
1955:
3019:
2954:
2934:
2919:
2899:
2883:
2781:
2712:
2702:
2661:
2546:
2516:
2018:
2013:
1358:
1266:
628:
262:
221:
1929:
3279:
3223:
3203:
3188:
3147:
3024:
2984:
2949:
2873:
2812:
2791:
2732:
2722:
2707:
2641:
2586:
2576:
2571:
2481:
2155:
2151:
2084:
2061:
1909:
1889:
1822:
1335:
1315:
1295:
1246:
1226:
1202:
1196:
1178:
1172:
870:
850:
830:
807:
787:
767:
744:
721:
689:
669:
638:
427:
227:
66:
28:
3341:
3284:
3142:
3083:
3014:
3004:
2999:
2924:
2853:
2727:
2717:
2646:
2566:
2551:
2486:
2370:
2278:
The density of unimodular matrices over integrally closed subrings of function fields
2223:
2191:
891:
It was realized later that these conditions define an incidence matrix of a balanced
664:
266:
245:
63:
3167:
3124:
3029:
2742:
2681:
2591:
2471:
2052:
929:
is TU. (The same holds for columns since the transpose of a TU matrix is also TU.)
903:
892:
2265:, Linear Algebra and its applications, vol. 434, Elsevier, pp. 1319–1324
2120:
17:
48:
Integer matrices with +1 or -1 determinant; invertible over the integers. GL_n(Z)
3009:
2979:
2747:
2581:
2451:
2083:
Heller, I.; Tompkins, C.B. (1956), "An
Extension of a Theorem of Dantzig's", in
1814:
1332:
is totally unimodular if and only if every simple arbitrarily-oriented cycle in
70:
52:
1129:(which is a row vector of the same width as the matrix) has all its entries in
3060:
2521:
2136:
3294:
2868:
1802:
totally unimodular, since it has a square submatrix of determinant −2.
412:
403:
910:
problems yield a coefficient matrix with these properties (and with empty
3228:
206:
2309:
Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Section 13.2",
78:
2376:
Software for testing total unimodularity by M. Walter and K. Truemper
1220:
434:(has an integral optimum, when any optimum exists). Specifically, if
2375:
2295:, Linear algebra and its applications, Elsevier, pp. 2675–2682
2154:, J.B. (1956), "Integral Boundary Points of Convex Polyhedra", in
291:
of two unimodular matrices is also unimodular. This follows since
2380:
1042:
5. Ghouila-Houri showed that a matrix is TU iff for every subset
2384:
574:
is integral, every extreme point of the feasible region (e.g.
2240:(rev. 3rd ed.). Springer. p. 510, Section XIII.3.
2293:
The probability of rectangular unimodular matrices over Fq
1926:
matrix is said to be unimodular if it can be extended with
2263:
Natural
Density of Rectangular Unimodular Integer Matrices
363:{\displaystyle \det(A\otimes B)=(\det A)^{q}(\det B)^{p},}
936:
is TU. The rows of a network matrix correspond to a tree
2366:
Mathematical
Programming Glossary by Harvey J. Greenberg
501:{\displaystyle \{\min c^{\top }x\mid Ax\geq b,x\geq 0\}}
73:+1 or −1. Equivalently, it is an integer matrix that is
761:
contains at most two non-zero (i.e., +1 or −1) entries;
418:
Totally unimodular matrices are extremely important in
2312:
2208:, P. D. (1980), "Decomposition of regular matroids",
2004:
to mean matrices that are invertible over the field.
1958:
1932:
1912:
1892:
1853:
1825:
1655:
1433:
1382:
1361:
1352:
consists of alternating forwards and backwards arcs.
1338:
1318:
1298:
1269:
1249:
1229:
1205:
1181:
1135:
1087:
1052:
873:
853:
833:
810:
790:
770:
747:
724:
692:
672:
641:
580:
514:
448:
297:
190:{\displaystyle \operatorname {GL} _{n}(\mathbb {Z} )}
162:
140:
2352:
276:
The unimodular matrix used (possibly implicitly) in
3252:
3176:
3122:
3058:
2892:
2810:
2756:
2695:
2419:
2315:, Mineola, N.Y.: Dover Publications, p. 316,
1971:
1944:
1918:
1898:
1878:
1831:
1787:
1621:
1416:and some copies of a particular 5-by-5 TU matrix.
1397:
1367:
1344:
1324:
1304:
1284:
1255:
1235:
1211:
1187:
1156:
1121:
1073:
879:
859:
847:have opposite signs, then the rows of both are in
839:
816:
796:
776:
753:
730:
706:. Then the following four conditions together are
698:
678:
647:
615:) is integral and thus the feasible region is an
607:
554:
500:
362:
189:
148:
255:the three transformation matrices in the ternary
27:This article is about matrices whose entries are
1424:1. The following matrix is totally unimodular:
631:, which is the coefficient matrix for bipartite
555:{\displaystyle \{\max c^{\top }x\mid Ax\leq b\}}
518:
452:
442:is integral, then linear programs of forms like
341:
322:
298:
85:that is its inverse (these are equivalent under
399:(TU matrix) is a matrix for which every square
784:have the same sign, then the row of one is in
663:matrix whose rows can be partitioned into two
217:, i.e. the following matrices are unimodular:
2396:
426:since they give a quick way to verify that a
8:
2261:Rosenthal, J.; Maze, G.; Wagner, U. (2011),
2066:Integral Boundary Points of Convex Polyhedra
1151:
1136:
602:
581:
549:
515:
495:
449:
111:is unimodular, has an integer solution. The
2970:Fundamental (linear differential equation)
2403:
2389:
2381:
2070:50 Years of Integer Programming, 1958-2008
1879:{\displaystyle \operatorname {GL} _{n}(R)}
2190:
1963:
1957:
1931:
1911:
1891:
1858:
1852:
1824:
1813:considers matrices with entries from any
1666:
1654:
1444:
1432:
1381:
1360:
1337:
1317:
1297:
1268:
1248:
1228:
1204:
1180:
1134:
1092:
1086:
1051:
963:").The columns correspond to another set
872:
852:
832:
809:
789:
769:
746:
723:
691:
671:
640:
579:
525:
513:
459:
447:
351:
332:
296:
180:
179:
167:
161:
142:
141:
139:
2333:Theory of Linear and Integer Programming
2121:"Incidence matrices and interval graphs"
1081:of signs to rows so that the signed sum
627:1. The unoriented incidence matrix of a
407:has only 0, +1 or −1 entries. The
3275:Matrix representation of conic sections
2164:Linear Inequalities and Related Systems
2119:Fulkerson, D. R.; Gross, O. A. (1965).
2093:Linear Inequalities and Related Systems
2044:
827:If two non-zero entries in a column of
764:If two non-zero entries in a column of
2105:T. Zaslavsky (1982), "Signed graphs,"
1175:proved the following theorem. Suppose
2068:", in M. Jünger; et al. (eds.),
921:3. The consecutive-ones property: if
257:tree of primitive Pythagorean triples
7:
261:Certain transformation matrices for
2179:Linear Algebra and Its Applications
1122:{\displaystyle \sum _{r\in R}s(r)r}
955:such that the tree is "rooted into
2276:Micheli, G.; Schnyder, R. (2016),
1636:problem on the following network:
623:Common totally unimodular matrices
608:{\displaystyle \{x\mid Ax\geq b\}}
526:
460:
25:
2072:, Springer-Verlag, pp. 49–50
107:both have integer components and
3309:
2371:Unimodular Matrix from MathWorld
1639:
1046:of rows, there is an assignment
3177:Used in science and engineering
2211:Journal of Combinatorial Theory
1979:to a unimodular square matrix.
1263:is the 0-1 incidence matrix of
967:of arcs on the same vertex set
201:Examples of unimodular matrices
2420:Explicitly constrained entries
2125:Pacific Journal of Mathematics
2064:, J. (2010), "Introduction to
1873:
1867:
1279:
1273:
1113:
1107:
1062:
1039:See more in Schrijver (2003).
971:. To compute the entry at row
562:have integral optima, for any
348:
338:
329:
319:
313:
301:
269:(both with determinant 1) and
184:
176:
1:
3194:Fundamental (computer vision)
916:multi-commodity flow problems
81:: there is an integer matrix
2224:10.1016/0095-8956(80)90075-1
2192:10.1016/0024-3795(84)90147-2
2107:Discrete Applied Mathematics
1164:(i.e. the row-submatrix has
1074:{\displaystyle s:R\to \pm 1}
149:{\displaystyle \mathbb {Z} }
41:Unimodular polynomial matrix
2960:Duplication and elimination
2759:eigenvalues or eigenvectors
1646:2. Any matrix of the form
1355:7. Suppose a matrix has 0-(
1157:{\displaystyle \{0,\pm 1\}}
205:Unimodular matrices form a
119:unimodular matrices form a
3364:
2893:With specific applications
2522:Discrete Fourier Transform
2291:Guo, X.; Yang, G. (2013),
714:to be totally unimodular:
570:is totally unimodular and
424:combinatorial optimization
237:of two unimodular matrices
26:
3303:
3184:Cabibbo–Kobayashi–Maskawa
2811:Satisfying conditions on
2335:. John Wiley & Sons,
397:totally unimodular matrix
1990:has the same meaning as
1788:{\displaystyle A=\left.}
1622:{\displaystyle A=\left.}
420:polyhedral combinatorics
241:Other examples include:
2542:Generalized permutation
2051:The term was coined by
1811:Abstract linear algebra
1806:Abstract linear algebra
1398:{\displaystyle 0,\pm 1}
89:). Thus every equation
3316:Mathematics portal
2029:Total dual integrality
1973:
1946:
1920:
1900:
1880:
1833:
1789:
1623:
1399:
1369:
1346:
1326:
1306:
1286:
1257:
1237:
1213:
1189:
1158:
1123:
1075:
881:
861:
841:
818:
798:
778:
755:
732:
700:
680:
649:
609:
556:
502:
378:are the dimensions of
364:
230:of a unimodular matrix
191:
150:
2109:4, pp. 401–406.
1974:
1972:{\displaystyle R^{m}}
1947:
1921:
1901:
1881:
1834:
1790:
1624:
1400:
1370:
1347:
1327:
1307:
1287:
1258:
1238:
1214:
1190:
1159:
1124:
1076:
1020:appears backwards in
1001:; then the entry is:
882:
862:
842:
819:
799:
779:
756:
733:
701:
681:
650:
610:
557:
503:
365:
215:matrix multiplication
192:
151:
2236:Lang, Serge (2002).
2024:Special linear group
1956:
1930:
1910:
1890:
1851:
1823:
1653:
1431:
1380:
1368:{\displaystyle \pm }
1359:
1336:
1316:
1296:
1285:{\displaystyle V(G)}
1267:
1247:
1227:
1203:
1199:without 2-dicycles,
1179:
1133:
1085:
1050:
871:
851:
831:
808:
788:
768:
745:
722:
690:
670:
639:
578:
512:
446:
295:
251:Permutation matrices
211:general linear group
160:
138:
132:general linear group
3265:Linear independence
2512:Diagonally dominant
2348:Alexander Schrijver
2329:Alexander Schrijver
2034:Hermite normal form
1945:{\displaystyle m-k}
1031:does not appear in
1009:appears forward in
804:, and the other in
391:Total unimodularity
282:Hermite normal form
156:, which is denoted
37:polynomial matrices
35:in connection with
3270:Matrix exponential
3260:Jordan normal form
3094:Fisher information
2965:Euclidean distance
2879:Totally unimodular
1969:
1942:
1916:
1896:
1876:
1829:
1785:
1776:
1619:
1610:
1395:
1365:
1342:
1322:
1302:
1282:
1253:
1233:
1219:is the set of all
1209:
1185:
1154:
1119:
1103:
1071:
877:
857:
837:
814:
794:
774:
751:
728:
696:
676:
645:
605:
552:
498:
360:
187:
146:
31:. For use of term
18:Totally unimodular
3335:
3334:
3327:Category:Matrices
3199:Fuzzy associative
3089:Doubly stochastic
2797:Positive-definite
2477:Block tridiagonal
2322:978-0-486-40258-1
1919:{\displaystyle m}
1899:{\displaystyle k}
1832:{\displaystyle R}
1420:Concrete examples
1345:{\displaystyle G}
1325:{\displaystyle A}
1305:{\displaystyle P}
1256:{\displaystyle A}
1236:{\displaystyle G}
1212:{\displaystyle P}
1188:{\displaystyle G}
1088:
908:minimum cost flow
880:{\displaystyle C}
860:{\displaystyle B}
840:{\displaystyle A}
817:{\displaystyle C}
797:{\displaystyle B}
777:{\displaystyle A}
754:{\displaystyle A}
731:{\displaystyle A}
699:{\displaystyle C}
679:{\displaystyle B}
648:{\displaystyle A}
289:Kronecker product
278:lattice reduction
273:(determinant −1).
57:unimodular matrix
16:(Redirected from
3355:
3322:List of matrices
3314:
3313:
3290:Row echelon form
3234:State transition
3163:Seidel adjacency
3045:Totally positive
2905:Alternating sign
2502:Complex Hadamard
2405:
2398:
2391:
2382:
2355:
2325:
2297:
2296:
2288:
2282:
2281:
2273:
2267:
2266:
2258:
2252:
2251:
2233:
2227:
2226:
2202:
2196:
2195:
2194:
2174:
2168:
2167:
2147:
2141:
2140:
2116:
2110:
2103:
2097:
2096:
2080:
2074:
2073:
2049:
1978:
1976:
1975:
1970:
1968:
1967:
1951:
1949:
1948:
1943:
1925:
1923:
1922:
1917:
1905:
1903:
1902:
1897:
1886:. A rectangular
1885:
1883:
1882:
1877:
1863:
1862:
1838:
1836:
1835:
1830:
1794:
1792:
1791:
1786:
1781:
1777:
1769:
1763:
1722:
1716:
1675:
1669:
1643:
1628:
1626:
1625:
1620:
1615:
1611:
1414:network matrices
1404:
1402:
1401:
1396:
1374:
1372:
1371:
1366:
1351:
1349:
1348:
1343:
1331:
1329:
1328:
1323:
1311:
1309:
1308:
1303:
1291:
1289:
1288:
1283:
1262:
1260:
1259:
1254:
1242:
1240:
1239:
1234:
1218:
1216:
1215:
1210:
1194:
1192:
1191:
1186:
1163:
1161:
1160:
1155:
1128:
1126:
1125:
1120:
1102:
1080:
1078:
1077:
1072:
984:
950:
886:
884:
883:
878:
866:
864:
863:
858:
846:
844:
843:
838:
823:
821:
820:
815:
803:
801:
800:
795:
783:
781:
780:
775:
760:
758:
757:
752:
741:Every column of
738:is 0, +1, or −1;
737:
735:
734:
729:
705:
703:
702:
697:
685:
683:
682:
677:
654:
652:
651:
646:
614:
612:
611:
606:
561:
559:
558:
553:
530:
529:
507:
505:
504:
499:
464:
463:
369:
367:
366:
361:
356:
355:
337:
336:
196:
194:
193:
188:
183:
172:
171:
155:
153:
152:
147:
145:
98:
21:
3363:
3362:
3358:
3357:
3356:
3354:
3353:
3352:
3338:
3337:
3336:
3331:
3308:
3299:
3248:
3172:
3118:
3054:
2888:
2806:
2752:
2691:
2492:Centrosymmetric
2415:
2409:
2362:
2346:
2323:
2308:
2305:
2300:
2290:
2289:
2285:
2275:
2274:
2270:
2260:
2259:
2255:
2248:
2235:
2234:
2230:
2204:
2203:
2199:
2176:
2175:
2171:
2162:, A.W. (eds.),
2150:Hoffman, A.J.;
2149:
2148:
2144:
2118:
2117:
2113:
2104:
2100:
2091:, A.W. (eds.),
2082:
2081:
2077:
2056:
2050:
2046:
2042:
2019:Regular matroid
2014:Balanced matrix
2010:
1959:
1954:
1953:
1928:
1927:
1908:
1907:
1888:
1887:
1854:
1849:
1848:
1821:
1820:
1808:
1775:
1774:
1768:
1761:
1760:
1755:
1747:
1742:
1734:
1728:
1727:
1721:
1714:
1713:
1708:
1700:
1695:
1687:
1681:
1680:
1674:
1662:
1651:
1650:
1609:
1608:
1600:
1592:
1584:
1579:
1574:
1568:
1567:
1562:
1554:
1549:
1541:
1533:
1527:
1526:
1521:
1516:
1508:
1500:
1495:
1486:
1485:
1477:
1472:
1467:
1462:
1454:
1440:
1429:
1428:
1422:
1378:
1377:
1357:
1356:
1334:
1333:
1314:
1313:
1294:
1293:
1265:
1264:
1245:
1244:
1225:
1224:
1201:
1200:
1177:
1176:
1171:6. Hoffman and
1131:
1130:
1083:
1082:
1048:
1047:
976:
937:
869:
868:
849:
848:
829:
828:
806:
805:
786:
785:
766:
765:
743:
742:
720:
719:
718:Every entry in
688:
687:
668:
667:
637:
636:
629:bipartite graph
625:
576:
575:
521:
510:
509:
455:
444:
443:
393:
386:, respectively.
347:
328:
293:
292:
246:Pascal matrices
222:Identity matrix
203:
163:
158:
157:
136:
135:
127: ×
115: ×
90:
49:
44:
29:integer numbers
23:
22:
15:
12:
11:
5:
3361:
3359:
3351:
3350:
3340:
3339:
3333:
3332:
3330:
3329:
3324:
3319:
3304:
3301:
3300:
3298:
3297:
3292:
3287:
3282:
3280:Perfect matrix
3277:
3272:
3267:
3262:
3256:
3254:
3250:
3249:
3247:
3246:
3241:
3236:
3231:
3226:
3221:
3216:
3211:
3206:
3201:
3196:
3191:
3186:
3180:
3178:
3174:
3173:
3171:
3170:
3165:
3160:
3155:
3150:
3145:
3140:
3135:
3129:
3127:
3120:
3119:
3117:
3116:
3111:
3106:
3101:
3096:
3091:
3086:
3081:
3076:
3071:
3065:
3063:
3056:
3055:
3053:
3052:
3050:Transformation
3047:
3042:
3037:
3032:
3027:
3022:
3017:
3012:
3007:
3002:
2997:
2992:
2987:
2982:
2977:
2972:
2967:
2962:
2957:
2952:
2947:
2942:
2937:
2932:
2927:
2922:
2917:
2912:
2907:
2902:
2896:
2894:
2890:
2889:
2887:
2886:
2881:
2876:
2871:
2866:
2861:
2856:
2851:
2846:
2841:
2836:
2827:
2821:
2819:
2808:
2807:
2805:
2804:
2799:
2794:
2789:
2787:Diagonalizable
2784:
2779:
2774:
2769:
2763:
2761:
2757:Conditions on
2754:
2753:
2751:
2750:
2745:
2740:
2735:
2730:
2725:
2720:
2715:
2710:
2705:
2699:
2697:
2693:
2692:
2690:
2689:
2684:
2679:
2674:
2669:
2664:
2659:
2654:
2649:
2644:
2639:
2637:Skew-symmetric
2634:
2632:Skew-Hermitian
2629:
2624:
2619:
2614:
2609:
2604:
2599:
2594:
2589:
2584:
2579:
2574:
2569:
2564:
2559:
2554:
2549:
2544:
2539:
2534:
2529:
2524:
2519:
2514:
2509:
2504:
2499:
2494:
2489:
2484:
2479:
2474:
2469:
2467:Block-diagonal
2464:
2459:
2454:
2449:
2444:
2442:Anti-symmetric
2439:
2437:Anti-Hermitian
2434:
2429:
2423:
2421:
2417:
2416:
2410:
2408:
2407:
2400:
2393:
2385:
2379:
2378:
2373:
2368:
2361:
2360:External links
2358:
2357:
2356:
2344:
2343:(mathematical)
2326:
2321:
2304:
2301:
2299:
2298:
2283:
2268:
2253:
2246:
2228:
2218:(3): 305–359,
2197:
2169:
2142:
2131:(3): 835–855.
2111:
2098:
2075:
2043:
2041:
2038:
2037:
2036:
2031:
2026:
2021:
2016:
2009:
2006:
1966:
1962:
1941:
1938:
1935:
1915:
1895:
1875:
1872:
1869:
1866:
1861:
1857:
1828:
1807:
1804:
1796:
1795:
1784:
1780:
1773:
1770:
1767:
1764:
1762:
1759:
1756:
1754:
1751:
1748:
1746:
1743:
1741:
1738:
1735:
1733:
1730:
1729:
1726:
1723:
1720:
1717:
1715:
1712:
1709:
1707:
1704:
1701:
1699:
1696:
1694:
1691:
1688:
1686:
1683:
1682:
1679:
1676:
1673:
1670:
1668:
1665:
1661:
1658:
1630:
1629:
1618:
1614:
1607:
1604:
1601:
1599:
1596:
1593:
1591:
1588:
1585:
1583:
1580:
1578:
1575:
1573:
1570:
1569:
1566:
1563:
1561:
1558:
1555:
1553:
1550:
1548:
1545:
1542:
1540:
1537:
1534:
1532:
1529:
1528:
1525:
1522:
1520:
1517:
1515:
1512:
1509:
1507:
1504:
1501:
1499:
1496:
1494:
1491:
1488:
1487:
1484:
1481:
1478:
1476:
1473:
1471:
1468:
1466:
1463:
1461:
1458:
1455:
1453:
1450:
1447:
1446:
1443:
1439:
1436:
1421:
1418:
1394:
1391:
1388:
1385:
1364:
1341:
1321:
1301:
1281:
1278:
1275:
1272:
1252:
1232:
1208:
1197:directed graph
1184:
1153:
1150:
1147:
1144:
1141:
1138:
1118:
1115:
1112:
1109:
1106:
1101:
1098:
1095:
1091:
1070:
1067:
1064:
1061:
1058:
1055:
1037:
1036:
1025:
1014:
985:, look at the
934:network matrix
889:
888:
876:
856:
836:
825:
813:
793:
773:
762:
750:
739:
727:
695:
675:
644:
624:
621:
604:
601:
598:
595:
592:
589:
586:
583:
551:
548:
545:
542:
539:
536:
533:
528:
524:
520:
517:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
462:
458:
454:
451:
428:linear program
392:
389:
388:
387:
359:
354:
350:
346:
343:
340:
335:
331:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
285:
274:
259:
253:
248:
239:
238:
231:
224:
202:
199:
186:
182:
178:
175:
170:
166:
144:
67:integer matrix
47:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3360:
3349:
3346:
3345:
3343:
3328:
3325:
3323:
3320:
3318:
3317:
3312:
3306:
3305:
3302:
3296:
3293:
3291:
3288:
3286:
3285:Pseudoinverse
3283:
3281:
3278:
3276:
3273:
3271:
3268:
3266:
3263:
3261:
3258:
3257:
3255:
3253:Related terms
3251:
3245:
3244:Z (chemistry)
3242:
3240:
3237:
3235:
3232:
3230:
3227:
3225:
3222:
3220:
3217:
3215:
3212:
3210:
3207:
3205:
3202:
3200:
3197:
3195:
3192:
3190:
3187:
3185:
3182:
3181:
3179:
3175:
3169:
3166:
3164:
3161:
3159:
3156:
3154:
3151:
3149:
3146:
3144:
3141:
3139:
3136:
3134:
3131:
3130:
3128:
3126:
3121:
3115:
3112:
3110:
3107:
3105:
3102:
3100:
3097:
3095:
3092:
3090:
3087:
3085:
3082:
3080:
3077:
3075:
3072:
3070:
3067:
3066:
3064:
3062:
3057:
3051:
3048:
3046:
3043:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3021:
3018:
3016:
3013:
3011:
3008:
3006:
3003:
3001:
2998:
2996:
2993:
2991:
2988:
2986:
2983:
2981:
2978:
2976:
2973:
2971:
2968:
2966:
2963:
2961:
2958:
2956:
2953:
2951:
2948:
2946:
2943:
2941:
2938:
2936:
2933:
2931:
2928:
2926:
2923:
2921:
2918:
2916:
2913:
2911:
2908:
2906:
2903:
2901:
2898:
2897:
2895:
2891:
2885:
2882:
2880:
2877:
2875:
2872:
2870:
2867:
2865:
2862:
2860:
2857:
2855:
2852:
2850:
2847:
2845:
2842:
2840:
2837:
2835:
2831:
2828:
2826:
2823:
2822:
2820:
2818:
2814:
2809:
2803:
2800:
2798:
2795:
2793:
2790:
2788:
2785:
2783:
2780:
2778:
2775:
2773:
2770:
2768:
2765:
2764:
2762:
2760:
2755:
2749:
2746:
2744:
2741:
2739:
2736:
2734:
2731:
2729:
2726:
2724:
2721:
2719:
2716:
2714:
2711:
2709:
2706:
2704:
2701:
2700:
2698:
2694:
2688:
2685:
2683:
2680:
2678:
2675:
2673:
2670:
2668:
2665:
2663:
2660:
2658:
2655:
2653:
2650:
2648:
2645:
2643:
2640:
2638:
2635:
2633:
2630:
2628:
2625:
2623:
2620:
2618:
2615:
2613:
2610:
2608:
2605:
2603:
2602:Pentadiagonal
2600:
2598:
2595:
2593:
2590:
2588:
2585:
2583:
2580:
2578:
2575:
2573:
2570:
2568:
2565:
2563:
2560:
2558:
2555:
2553:
2550:
2548:
2545:
2543:
2540:
2538:
2535:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2498:
2495:
2493:
2490:
2488:
2485:
2483:
2480:
2478:
2475:
2473:
2470:
2468:
2465:
2463:
2460:
2458:
2455:
2453:
2450:
2448:
2445:
2443:
2440:
2438:
2435:
2433:
2432:Anti-diagonal
2430:
2428:
2425:
2424:
2422:
2418:
2413:
2406:
2401:
2399:
2394:
2392:
2387:
2386:
2383:
2377:
2374:
2372:
2369:
2367:
2364:
2363:
2359:
2353:
2349:
2345:
2342:
2341:0-471-98232-6
2338:
2334:
2330:
2327:
2324:
2318:
2314:
2313:
2307:
2306:
2302:
2294:
2287:
2284:
2279:
2272:
2269:
2264:
2257:
2254:
2249:
2247:0-387-95385-X
2243:
2239:
2232:
2229:
2225:
2221:
2217:
2213:
2212:
2207:
2201:
2198:
2193:
2188:
2184:
2180:
2173:
2170:
2165:
2161:
2157:
2153:
2146:
2143:
2138:
2134:
2130:
2126:
2122:
2115:
2112:
2108:
2102:
2099:
2094:
2090:
2086:
2079:
2076:
2071:
2067:
2063:
2059:
2054:
2048:
2045:
2039:
2035:
2032:
2030:
2027:
2025:
2022:
2020:
2017:
2015:
2012:
2011:
2007:
2005:
2003:
1999:
1995:
1994:
1989:
1985:
1980:
1964:
1960:
1939:
1936:
1933:
1913:
1893:
1870:
1864:
1859:
1855:
1846:
1842:
1826:
1819:
1816:
1812:
1805:
1803:
1801:
1782:
1778:
1771:
1765:
1757:
1752:
1749:
1744:
1739:
1736:
1731:
1724:
1718:
1710:
1705:
1702:
1697:
1692:
1689:
1684:
1677:
1671:
1663:
1659:
1656:
1649:
1648:
1647:
1644:
1642:
1637:
1635:
1616:
1612:
1605:
1602:
1597:
1594:
1589:
1586:
1581:
1576:
1571:
1564:
1559:
1556:
1551:
1546:
1543:
1538:
1535:
1530:
1523:
1518:
1513:
1510:
1505:
1502:
1497:
1492:
1489:
1482:
1479:
1474:
1469:
1464:
1459:
1456:
1451:
1448:
1441:
1437:
1434:
1427:
1426:
1425:
1419:
1417:
1415:
1411:
1406:
1392:
1389:
1386:
1383:
1362:
1353:
1339:
1319:
1299:
1276:
1270:
1250:
1230:
1222:
1206:
1198:
1182:
1174:
1169:
1167:
1148:
1145:
1142:
1139:
1116:
1110:
1104:
1099:
1096:
1093:
1089:
1068:
1065:
1059:
1056:
1053:
1045:
1040:
1034:
1030:
1026:
1023:
1019:
1015:
1012:
1008:
1004:
1003:
1002:
1000:
996:
992:
988:
983:
979:
974:
970:
966:
962:
959:" or "out of
958:
954:
948:
944:
940:
935:
930:
928:
924:
919:
917:
913:
909:
905:
901:
896:
894:
874:
867:, or both in
854:
834:
826:
811:
791:
771:
763:
748:
740:
725:
717:
716:
715:
713:
709:
693:
673:
666:
665:disjoint sets
662:
658:
642:
634:
630:
622:
620:
618:
599:
596:
593:
590:
587:
584:
573:
569:
565:
546:
543:
540:
537:
534:
531:
522:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
456:
441:
437:
433:
429:
425:
421:
416:
414:
410:
405:
402:
398:
390:
385:
381:
377:
373:
357:
352:
344:
333:
325:
316:
310:
307:
304:
290:
286:
283:
279:
275:
272:
268:
264:
260:
258:
254:
252:
249:
247:
244:
243:
242:
236:
232:
229:
225:
223:
220:
219:
218:
216:
212:
208:
200:
198:
173:
168:
164:
133:
130:
126:
122:
118:
114:
110:
106:
102:
97:
93:
88:
87:Cramer's rule
84:
80:
76:
72:
68:
65:
61:
58:
54:
46:
42:
38:
34:
30:
19:
3307:
3239:Substitution
3125:graph theory
2863:
2622:Quaternionic
2612:Persymmetric
2351:
2332:
2311:
2292:
2286:
2277:
2271:
2262:
2256:
2237:
2231:
2215:
2214:, Series B,
2209:
2200:
2182:
2178:
2172:
2163:
2145:
2128:
2124:
2114:
2106:
2101:
2092:
2078:
2069:
2065:
2053:Claude Berge
2047:
2002:non-singular
2001:
1997:
1993:non-singular
1991:
1987:
1981:
1809:
1799:
1797:
1645:
1638:
1634:maximum flow
1631:
1423:
1413:
1407:
1354:
1170:
1043:
1041:
1038:
1032:
1028:
1021:
1017:
1010:
1006:
998:
994:
990:
986:
981:
977:
972:
968:
964:
960:
956:
952:
946:
942:
938:
933:
931:
926:
922:
920:
911:
904:maximum flow
897:
893:signed graph
890:
711:
660:
656:
626:
619:polyhedron.
571:
567:
563:
439:
435:
417:
401:non-singular
396:
394:
383:
379:
375:
371:
284:of matrices.
240:
204:
128:
124:
116:
112:
108:
104:
100:
95:
91:
82:
59:
56:
50:
45:
32:
3214:Hamiltonian
3138:Biadjacency
3074:Correlation
2990:Householder
2940:Commutation
2677:Vandermonde
2672:Tridiagonal
2607:Permutation
2597:Nonnegative
2582:Matrix unit
2462:Bisymmetric
2185:: 253–266,
1847:is denoted
1815:commutative
1166:discrepancy
975:and column
900:constraints
566:. Hence if
280:and in the
123:called the
71:determinant
53:mathematics
3114:Transition
3109:Stochastic
3079:Covariance
3061:statistics
3040:Symplectic
3035:Similarity
2864:Unimodular
2859:Orthogonal
2844:Involutory
2839:Invertible
2834:Projection
2830:Idempotent
2772:Convergent
2667:Triangular
2617:Polynomial
2562:Hessenberg
2532:Equivalent
2527:Elementary
2507:Copositive
2497:Conference
2457:Bidiagonal
2354:, Springer
2303:References
1998:Unimodular
1988:unimodular
1016:−1 if arc
1005:+1 if arc
708:sufficient
438:is TU and
271:reflection
75:invertible
33:unimodular
3295:Wronskian
3219:Irregular
3209:Gell-Mann
3158:Laplacian
3153:Incidence
3133:Adjacency
3104:Precision
3069:Centering
2975:Generator
2945:Confusion
2930:Circulant
2910:Augmented
2869:Unipotent
2849:Nilpotent
2825:Congruent
2802:Stieltjes
2777:Defective
2767:Companion
2738:Redheffer
2657:Symmetric
2652:Sylvester
2627:Signature
2557:Hermitian
2537:Frobenius
2447:Arrowhead
2427:Alternant
2137:0030-8730
1937:−
1865:
1772:⋮
1766:⋮
1758:⋯
1750:−
1745:⋯
1732:⋯
1725:⋮
1719:⋮
1711:⋯
1698:⋯
1685:⋯
1678:⋮
1672:⋮
1603:−
1557:−
1511:−
1503:−
1457:−
1449:−
1390:±
1363:±
1146:±
1097:∈
1090:∑
1066:±
1063:→
1027:0 if arc
932:4. Every
597:≥
588:∣
544:≤
535:∣
527:⊤
490:≥
478:≥
469:∣
461:⊤
413:transpose
404:submatrix
308:⊗
174:
77:over the
3348:Matrices
3342:Category
3123:Used in
3059:Used in
3020:Rotation
2995:Jacobian
2955:Distance
2935:Cofactor
2920:Carleman
2900:Adjugate
2884:Weighing
2817:inverses
2813:products
2782:Definite
2713:Identity
2703:Exchange
2696:Constant
2662:Toeplitz
2547:Hadamard
2517:Diagonal
2350:(2003),
2331:(1998),
2158:, H.W.;
2087:, H.W.;
2060:, A.J.;
2008:See also
1952:rows in
633:matching
617:integral
432:integral
409:converse
267:shearing
263:rotation
207:subgroup
99:, where
79:integers
3224:Overlap
3189:Density
3148:Edmonds
3025:Seifert
2985:Hessian
2950:Coxeter
2874:Unitary
2792:Hurwitz
2723:Of ones
2708:Hilbert
2642:Skyline
2587:Metzler
2577:Logical
2572:Integer
2482:Boolean
2414:classes
2238:Algebra
2206:Seymour
2152:Kruskal
2062:Kruskal
2058:Hoffman
1982:Over a
1843:. This
1410:Seymour
1312:. Then
1292:versus
1221:dipaths
1173:Kruskal
898:2. The
415:is TU.
235:product
228:inverse
209:of the
69:having
3143:Degree
3084:Design
3015:Random
3005:Payoff
3000:Moment
2925:Cartan
2915:Bézout
2854:Normal
2728:Pascal
2718:Lehmer
2647:Sparse
2567:Hollow
2552:Hankel
2487:Cauchy
2412:Matrix
2339:
2319:
2244:
2160:Tucker
2135:
2089:Tucker
2055:, see
1243:, and
655:be an
370:where
213:under
64:square
39:, see
3204:Gamma
3168:Tutte
3030:Shear
2743:Shift
2733:Pauli
2682:Walsh
2592:Moore
2472:Block
2040:Notes
1984:field
1845:group
1195:is a
993:path
686:and
134:over
121:group
62:is a
3010:Pick
2980:Gram
2748:Zero
2452:Band
2337:ISBN
2317:ISBN
2242:ISBN
2156:Kuhn
2133:ISSN
2085:Kuhn
1906:-by-
1841:unit
1818:ring
989:-to-
906:and
710:for
422:and
382:and
374:and
287:The
233:The
226:The
103:and
55:, a
3099:Hat
2832:or
2815:or
2220:doi
2187:doi
1800:not
1798:is
1408:8.
1223:in
997:in
941:= (
902:of
659:by
519:max
508:or
453:min
430:is
342:det
323:det
299:det
51:In
3344::
2216:28
2183:63
2181:,
2129:15
2127:.
2123:.
1996:.
1986:,
1856:GL
1405:.
982:st
980:=
945:,
395:A
265:,
197:.
165:GL
94:=
92:Mx
3229:S
2687:Z
2404:e
2397:t
2390:v
2250:.
2222::
2189::
2139:.
1965:m
1961:R
1940:k
1934:m
1914:m
1894:k
1874:)
1871:R
1868:(
1860:n
1827:R
1783:.
1779:]
1753:1
1740:1
1737:+
1706:1
1703:+
1693:1
1690:+
1664:[
1660:=
1657:A
1617:.
1613:]
1606:1
1598:1
1595:+
1590:1
1587:+
1582:0
1577:0
1572:0
1565:0
1560:1
1552:0
1547:1
1544:+
1539:1
1536:+
1531:0
1524:0
1519:0
1514:1
1506:1
1498:0
1493:1
1490:+
1483:1
1480:+
1475:0
1470:0
1465:0
1460:1
1452:1
1442:[
1438:=
1435:A
1393:1
1387:,
1384:0
1340:G
1320:A
1300:P
1280:)
1277:G
1274:(
1271:V
1251:A
1231:G
1207:P
1183:G
1152:}
1149:1
1143:,
1140:0
1137:{
1117:r
1114:)
1111:r
1108:(
1105:s
1100:R
1094:r
1069:1
1060:R
1057::
1054:s
1044:R
1035:.
1033:P
1029:R
1024:,
1022:P
1018:R
1013:,
1011:P
1007:R
999:T
995:P
991:t
987:s
978:C
973:R
969:V
965:C
961:r
957:r
953:r
949:)
947:R
943:V
939:T
927:A
923:A
912:C
887:.
875:C
855:B
835:A
824:;
812:C
792:B
772:A
749:A
726:A
712:A
694:C
674:B
661:n
657:m
643:A
603:}
600:b
594:x
591:A
585:x
582:{
572:b
568:A
564:c
550:}
547:b
541:x
538:A
532:x
523:c
516:{
496:}
493:0
487:x
484:,
481:b
475:x
472:A
466:x
457:c
450:{
440:b
436:A
384:B
380:A
376:q
372:p
358:,
353:p
349:)
345:B
339:(
334:q
330:)
326:A
320:(
317:=
314:)
311:B
305:A
302:(
185:)
181:Z
177:(
169:n
143:Z
129:n
125:n
117:n
113:n
109:M
105:b
101:M
96:b
83:N
60:M
43:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.