Fact-checked by Grok 2 weeks ago

Unimodular matrix

A unimodular matrix is a square matrix with integer entries whose determinant is either +1 or -1.^[1] This property ensures that the matrix is invertible over the integers, meaning its inverse is also an integer matrix.^[2] The set of all n × n unimodular matrices forms the general linear group GL(n, ℤ), which consists of all invertible n × n matrices over the ring of integers under matrix multiplication.^[3] This group plays a fundamental role in number theory and algebra, as its elements represent automorphisms of the integer lattice ℤⁿ, preserving the lattice structure under linear transformations.^[4] Unimodular matrices arise naturally in the study of lattices, where they describe changes of basis that maintain the same lattice points.^[5] Beyond lattice theory, unimodular matrices have applications in integer programming and optimization, where they facilitate transformations between equivalent integer linear programs while preserving integrality.^[6] In computational contexts, such as compiler design for loop optimizations, unimodular transformations enable efficient reordering of iterations without altering program semantics.^[7] Their group structure also underpins modular arithmetic and the study of arithmetic groups in geometry and topology.^[8]

Definitions and Properties

Definition

A unimodular matrix is a square matrix with integer entries whose determinant is either +1 or −1.^[9] The term "unimodular" derives from ring theory, where such a matrix over a commutative ring generates the unit ideal, meaning its columns form a basis for the free module over the ring; for the ring of integers \mathbb{Z}, this corresponds to the determinant being a unit, i.e., \pm 1.^[10] Equivalently, unimodular matrices are precisely the integer matrices that are invertible over \mathbb{Z}, with the inverse also having integer entries.^[9] The set of all n \times n unimodular matrices forms the general linear group \mathrm{GL}(n, \mathbb{Z}), while those with determinant exactly +1 constitute the special linear group \mathrm{SL}(n, \mathbb{Z}).^[11]^[12] This distinguishes unimodular matrices from general integer matrices, which may have determinants of arbitrary integer value and lack invertibility over \mathbb{Z}. Total unimodularity extends this concept to rectangular matrices where every square submatrix has determinant 0, \pm 1.^[9]

Basic Properties

A unimodular matrix A \in \mathbb{Z}^{n \times n} with \det(A) = \pm 1 is invertible over the integers, meaning its inverse A^{-1} also has integer entries. This follows from the formula A^{-1} = \frac{1}{\det(A)} \adj(A), where the adjugate \adj(A) consists of cofactors that are themselves determinants of integer submatrices and thus integers, and division by \det(A) = \pm 1 yields integers.^[9] Consequently, A induces a bijection on the integer lattice \mathbb{Z}^n, mapping it to itself while preserving its structure as a free \mathbb{Z}-module of rank n. In particular, the columns of A form a \mathbb{Z}-basis for \mathbb{Z}^n, equivalent to the standard basis up to integer linear combinations that maintain the lattice volume. The set of all unimodular matrices forms the general linear group \mathrm{GL}(n, \mathbb{Z}) under matrix multiplication, implying that the product of any two unimodular matrices A and B is again unimodular, as \det(AB) = \det(A) \det(B) = (\pm 1)(\pm 1) = \pm 1.^[9] Similarly, the transpose A^T of a unimodular matrix A is unimodular, since \det(A^T) = \det(A) = \pm 1 and A^T has integer entries. As a direct consequence of integer invertibility, the linear system Ax = b with A unimodular and b \in \mathbb{Z}^n admits a unique solution x \in \mathbb{Z}^n, given explicitly by x = A^{-1} b. This solvability over \mathbb{Z} underscores the role of unimodular matrices in preserving integrality in linear transformations. The subset of unimodular matrices with \det(A) = 1 constitutes the special linear group \mathrm{SL}(n, \mathbb{Z}).^[9]

Examples and Constructions

Elementary Examples

The simplest unimodular matrices are the 1×1 cases, namely the matrices

{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}

and [-1], each with determinant \pm 1.^[9] In the 2×2 case, the identity matrix I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} has determinant $1, confirming its unimodularity, while its negative -I_2 = \begin{pmatrix} -1 & 0 \ 0 & -1 \end{pmatrix}

has determinant &#36;1

as the product of the diagonals.^[9] More generally, any diagonal matrix with \pm 1 entries on the diagonal is unimodular, since the determinant equals the product of these entries, yielding \pm 1; for instance, \operatorname{diag}(1, -1) = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} has determinant -1.^[13] Permutation matrices provide another elementary class of unimodular matrices, as their determinants equal the sign of the corresponding permutation, which is \pm 1. For example, the 2×2 swap matrix P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, corresponding to the transposition (1\ 2), has determinant \det(P) = 0 \cdot 0 - 1 \cdot 1 = -1.^[13] A non-diagonal example is the shear matrix A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, an upper triangular integer matrix with determinant \det(A) = 1 \cdot 1 - 1 \cdot 0 = 1, hence unimodular.^[14]

Constructions from Permutations and Signs

One method to construct unimodular matrices involves generating elements of the general linear group GL(2, \mathbb{Z}), which consists of all 2 \times 2 integer matrices with determinant \pm 1. This group is generated by elementary matrices, including shear transformations such as the transvection matrix T = \begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix} and reflection matrices that introduce sign changes, such as the diagonal matrix D = \begin{pmatrix} -1 & 0 \ 0 & 1 \end{pmatrix}. By taking products of these generators, any matrix in GL(2, \mathbb{Z}) can be obtained, as the elementary operations suffice to produce all invertible integer matrices with the required determinant.^[15] A specific class of unimodular matrices arises from signed permutation matrices, which are obtained by permuting the rows or columns of the identity matrix and then multiplying selected entries by -1. Formally, such a matrix can be expressed as the product PD, where P is a standard permutation matrix and D is a diagonal matrix with entries \pm 1 on the diagonal. These matrices have exactly one nonzero entry in each row and each column, with that entry being \pm 1.^[16] The determinant of a signed permutation matrix PD is given by \det(PD) = \det(P) \det(D) = \operatorname{sgn}(\sigma) \prod_{i=1}^n d_{ii}, where \sigma is the permutation corresponding to P and each d_{ii} = \pm 1. Since \operatorname{sgn}(\sigma) = \pm 1 and the product of the d_{ii} is also \pm 1, the overall determinant is \pm 1, confirming unimodularity.^[17] For example, starting from the 2 \times 2 identity matrix I = \begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix} (which has \det = 1), one can apply a row swap to obtain P = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix} (\det = -1) or multiply the second row by -1 to get \begin{pmatrix} 1 & 0 \ 0 & -1 \end{pmatrix} (\det = -1). Combining these, such as swapping rows and then flipping the sign of the first entry, yields matrices like \begin{pmatrix} 0 & 1 \ -1 & 0 \end{pmatrix} (\det = 1), covering both even and odd determinant cases through iterative applications.^[15] The collection of all signed permutation matrices forms the hyperoctahedral group, which is a finite subgroup of GL(n, \mathbb{Z}) isomorphic to the wreath product \mathbb{Z}_2 \wr S_n.^[16]

Total Unimodularity

Definition and Equivalence Conditions

A totally unimodular matrix is defined as an integer matrix A, not necessarily square, such that the determinant of every square submatrix of A is $0, +1, or -1.[19] This property ensures that all entries of Alie in{-1, 0, 1}, as each entry forms a 1 \times 1$ submatrix.^[18] The concept was introduced by Hoffman and Kruskal in 1956 specifically to address integrality conditions in linear programming with integer constraints.^[19] In contrast to a standard unimodular matrix, which is a square integer matrix with determinant \pm 1 (and thus an integer inverse), total unimodularity extends the notion to rectangular matrices and imposes the determinant condition on all square submatrices rather than solely the full matrix.^[20] For square matrices of full rank, total unimodularity implies the standard unimodularity property, but the converse does not hold; for instance, matrices with integer entries outside \{-1, 0, 1\} can have determinant \pm 1 yet fail the submatrix condition due to larger $1 \times 1 determinants.^[20] A key equivalence condition for total unimodularity, established by Hoffman and Kruskal, states that an integer matrix A is totally unimodular if and only if, for every integer vector b, the polyhedron \{ x \geq 0 \mid A x \leq b \} has integer vertices.^[18] This integrality property highlights the significance of total unimodularity in ensuring integer optimal solutions for certain linear programs without additional constraints.^[19] Unimodular matrices represent a special case of totally unimodular matrices when they are square and of full rank.^[20]

Characterization Theorems

A key characterization of totally unimodular matrices was provided by Ghouila-Houri in 1962. For a matrix A \in \{0, \pm 1\}^{m \times n}, A is totally unimodular if and only if for every subset of columns J \subseteq , there exists a partition of the rows into two sets R_1 and R_2 such that, for each column j \in J, the absolute value of the sum of the entries in the rows of R_1 is at most 1, and similarly for R_2.^[21] This condition ensures that no submatrix has a determinant outside \{ -1, 0, 1 \}, as violations would imply higher discrepancy in row sums after partitioning. Equivalently, this can be stated in terms of hereditary discrepancy: A is totally unimodular if and only if \text{herdisc}(A) \leq 1, where the hereditary discrepancy is the maximum discrepancy over all submatrices, and the discrepancy of a matrix is the minimum over signings x \in \{-1, 1\}^m of \| A x \|_\infty.^[22] A sufficient condition for (0,1)-matrices to be totally unimodular is the consecutive ones property: the rows can be permuted so that the 1-entries in each row form a consecutive block.^[23] This property ensures that the matrix represents an interval structure, avoiding forbidden submatrices with determinants of absolute value greater than 1. Network matrices provide a combinatorial characterization of totally unimodular matrices. The incidence matrix of a directed graph, where rows correspond to vertices and columns to arcs (with -1 at the tail, +1 at the head, and 0 elsewhere), is totally unimodular because every square submatrix satisfies the subdeterminant condition: its determinant is 0, +1, or -1.^[24] This follows from the fact that any square submatrix corresponds to a subgraph where the kernel of the submatrix relates to Eulerian paths or cycles, leading to determinants bounded by 1 in absolute value via expansion along tree-like structures or cycle cancellations. In the case of a bipartite graph, the incidence matrix B (biadjacency form, with entries 0 or 1) is totally unimodular.^[25] A classic example illustrating failure of total unimodularity is the submatrix \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, which has determinant -2. This violates the subdeterminant condition directly. Applying Ghouila-Houri's theorem, for the full set of rows and columns, no partition of the rows into R_1, R_2 satisfies the sum-of-absolute-values bound of at most 1 per column in each part, as any partition leads to at least one column with sum 2 in absolute value; equivalently, no row signing yields \| A x \|_\infty \leq 1, confirming the discrepancy exceeds 1.^[22]

Applications

In Integer Linear Programming

In integer linear programming (ILP), unimodular matrices facilitate transformations between equivalent formulations while preserving the integrality of solutions. A change of variables x = U y, where U is an n \times n unimodular matrix and y is integer-valued, transforms the constraint A x = b into A U y = b. Since U^{-1} is also an integer matrix, the integer solutions in y correspond exactly to integer solutions in x, maintaining the structure of the ILP without introducing fractional solutions.^[6] For square unimodular matrices, which are invertible over the integers with determinant \pm 1, the constraint A x = b with integer b admits a unique integer solution x = A^{-1} b. This follows from Cramer's rule, where the entries of the inverse are integers because all relevant determinants are \pm 1, ensuring exact integer solutions without fractional components.^[26] Unimodular matrices are also essential in computing normal forms for integer matrices, such as the Hermite normal form (HNF). For an integer matrix A, there exist unimodular matrices U such that A U = HNF(A), where the HNF is an upper triangular form with specific divisibility conditions. This decomposition solves systems of linear Diophantine equations A x = b in strongly polynomial time using GCD oracles, with applications in optimization for finding particular solutions and bases for the solution space. The process requires O(n^3) arithmetic operations and O(n^2) GCD calls for square systems, enabling efficient handling of integer constraints in ILP.^[6]

In Lattice Theory and Groups

In lattice theory, unimodular matrices precisely characterize the automorphisms of the integer lattice \mathbb{Z}^n. These automorphisms are linear transformations that map \mathbb{Z}^n to itself while preserving its additive group structure, achieved by integer matrices A with \det(A) = \pm 1, ensuring the standard basis vectors are sent to another \mathbb{Z}-basis of the lattice.^[27] Such transformations maintain the discrete nature of the lattice points and their linear independence over \mathbb{Z}. A key property of unimodular matrices is their preservation of volume in the lattice context. Since |\det(A)| = 1, applying A to a sublattice scales its covolume—the reciprocal of the determinant of the sublattice—by exactly 1, leaving the density of lattice points unchanged within the ambient space.^[27] This volume preservation is fundamental for equivalence classes of lattices, as it ensures that isomorphic lattices share the same geometric measure. In crystallography, unimodular transformations facilitate the classification of lattice types, such as Bravais classes, without altering the physical density of atoms or points per unit volume. For instance, in two-dimensional lattices, matrices in \mathrm{GL}_2(\mathbb{Z}) act on quadratic forms to identify symmetry-equivalent structures like p2 and p2mm, preserving the primitive cell volume and enabling systematic enumeration of crystal symmetries.^[28] Unimodular matrices also play a central role in the Smith normal form decomposition of integer matrices over \mathbb{Z}. For an m \times n integer matrix B, there exist unimodular matrices P \in \mathrm{GL}_m(\mathbb{Z}) and Q \in \mathrm{GL}_n(\mathbb{Z}) such that P B Q = D, where D is a diagonal matrix with non-negative entries satisfying the divisibility condition d_i \mid d_{i+1}. This diagonalization reveals the structure of the cokernel \mathbb{Z}^n / B \mathbb{Z}^m \cong \bigoplus_{i=1}^r \mathbb{Z}/d_i \mathbb{Z}, providing invariants for lattice quotients.^[29] In the study of toric varieties, unimodular triangulations of lattice polytopes rely on unimodular matrices to ensure preservation of integer points. A triangulation is unimodular if every simplex has volume $1/n! and contains no additional lattice points beyond its vertices, corresponding to affine coordinate changes via unimodular matrices that maintain the lattice structure in the fan. This property guarantees that the associated toric variety is smooth and projectively normal, with the integer points faithfully reflected in the combinatorial data.^[30]

Advanced Algebraic Aspects

Relation to Special Linear Group

The special linear group \mathrm{SL}(n, \mathbb{Z}) is defined as the kernel of the determinant homomorphism \det: \mathrm{GL}(n, \mathbb{Z}) \to \{\pm 1\}, consisting precisely of those unimodular matrices over \mathbb{Z} with determinant equal to $1. This makes \mathrm{SL}(n, \mathbb{Z})

a [normal subgroup](/page/Normal_subgroup) of [index](/page/Index) &#36;2

in \mathrm{GL}(n, \mathbb{Z}) for all n \geq 2, since the determinant map is surjective onto \{\pm 1\} and its kernel is exactly \mathrm{SL}(n, \mathbb{Z}).^[31] The group \mathrm{SL}(n, \mathbb{Z}) is generated by the elementary matrices E_{ij}(1) for i \neq j, where E_{ij}(1) is the identity matrix with a $1added in the(i,j)-entry; there are n^2 - nsuch generators in total. A key group-theoretic feature is the congruence subgroup property: the [quotient](/page/Quotient)\mathrm{SL}(n, \mathbb{Z}) / \Gamma(n, m)is finite for each principal [congruence subgroup](/page/Congruence_subgroup)\Gamma(n, m) = \ker(\mathrm{SL}(n, \mathbb{Z}) \to \mathrm{SL}(n, \mathbb{Z}/m\mathbb{Z})), where m \geq 1$, reflecting the arithmetic structure of these groups.^[32] For n=2, \mathrm{SL}(2, \mathbb{Z}) is known as the modular group (in its full form, including the center), and it admits the presentation \langle s, t \mid s^4 = 1, (st)^3 = s^2 \rangle, where s and t can be taken as the matrices \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} and \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, respectively, and s^2 = -I is the nontrivial central element.^[33] This presentation highlights the interplay between finite-order elements and relations arising from the action on the upper half-plane.^[33]

Invertibility over Integers

A unimodular matrix A \in M_n(\mathbb{Z}) is invertible over the integers, meaning its inverse A^{-1} also has integer entries. This follows from the adjugate formula A^{-1} = \frac{1}{\det(A)} \adj(A), where \adj(A) is the transpose of the cofactor matrix of A. Since A has integer entries, each cofactor is the determinant of an integer submatrix, hence an integer, making \adj(A) an integer matrix. With \det(A) = \pm 1, the scalar factor is also an integer, ensuring A^{-1} \in M_n(\mathbb{Z}).^[34] Two integer matrices are unimodularly equivalent over \mathbb{Z} if one can be obtained from the other by left or right multiplication by unimodular matrices; this equivalence preserves key invariants, such as the greatest common divisor of the k \times k minors for each k. Such transformations maintain the lattice structure spanned by the columns (or rows) of the matrices.^[35] Any integer matrix can be transformed into its Hermite normal form—a unique upper triangular form with specific non-negative diagonal and off-diagonal constraints—via right multiplication by a unimodular matrix. This reduction, achievable through elementary column operations (adding integer multiples of one column to another, scaling by \pm 1, or swapping columns), facilitates solving systems of linear Diophantine equations and computing lattice invariants.^[36] For a unimodular matrix A \in M_n(\mathbb{Z}), the ideal generated by its entries in \mathbb{Z} is the unit ideal \mathbb{Z}. This holds because \det(A) = \pm 1 lies in the ideal, as it equals the sum over i of a_{i1} C_{i1} (or similarly for other expansions), where the C_{ij} are integer cofactors.^[34] The notion of unimodularity generalizes to principal ideal domains (PIDs), where a square matrix over a PID is unimodular if its determinant is a unit in the PID. In such rings, including polynomial rings over fields, this ensures invertibility over the ring itself, with analogous properties for adjugates and ideals generated by maximal minors.^[37]

References

[1]
[PDF] Lecture 1 Introduction 1 Lattices
definition. DEFINITION 4 (UNIMODULAR MATRIX) A matrix U ∈ Zn×n is called unimodular if detU = ±1. For example, the matrix. µ. 1 2. 0 1. ¶ is unimodular. The ...
[2]
Chapter 2 Unimodular Matrices
A unimodular matrix is defined in such a way that its inverse is necessarily integral. We say that a square integer matrix A is unimodular if det(A) = ±1. This ...<|control11|><|separator|>
[3]
View of Conjugacy classes of torsion in GL_n(Z)
A unimodular matrix of sizenis ann×ninteger matrix having determinant+1 or−1.The general linear group of sizenoverZ, denoted byGLn(Z), is the setof ...
[4]
[PDF] Point Lattices - UCSD CSE
Then L(B) = L(C) if and only if there exists an invertible matrix U ∈ GL(n,Z) such that B = CU. ... So, let U be a unimodular matrix. By Corollary 9 there ...
[5]
[PDF] Lattices. - Purdue Computer Science
A unimodular matrix is one with determinant. ±1. It is easy to show that det(B′B′T ) = det(BB. T. ) ...
[6]
[PDF] Can a System of Linear Diophantine Equations be Solved in ...
Oct 17, 1994 · The unimodular matrix, Ua,b, allows our algorithm for finding the ... unimodular (as previously observed: integer valued, with determinant 1) ...
[7]
[PDF] Lecture Notes on Linear Cache Optimization & Vectorization
Nov 18, 2010 · Given a unimodular matrix U ∈ GL(n,Z), we can apply the corre- sponding transformation by multiplying the iteration vectors by U, which may ...
[8]
[PDF] ON FREDHOLM DETERMINANTS IN TOPOLOGY
Dec 23, 2016 · Because an unimodular matrix M is non-singular in the ring M(n, Z) of integer matrices, a unimodular matrix M is an element in GL(n, Z). Let ...<|control11|><|separator|>
[9]
[PDF] Lecture 6: Totally Unimodular Matrices - NC State ISE
• Definition: A matrix A is totally unimodular if every square non-singular submatrix is unimodular, i.e., every sub- determinant of A is either +1, -1, or ...
[10]
Root polynomials and their role in the theory of matrix polynomials
Jan 1, 2020 · ... matrix polynomial ring, its units are sometimes called unimodular matrix polynomials. It is straightforward to show that the units of F [ x ] ...
[11]
[PDF] General linear group
The special linear group, written SL(n, F) or SLn(F), is the subgroup of GL(n, F) consisting of matrices with a determinant of 1. The group GL(n, F) and its ...
[12]
Generating pairs for SL(n, Z) - ScienceDirect.com
Jan 15, 2025 · The special linear group SL ( n , Z ) is the multiplicative group of all n × n matrices with integer entries having determinant 1. It is well ...
[13]
[PDF] 18.06.23: Determinants & Permutations - MIT
Jun 18, 2023 · This is a general pattern: the determinant of a permutation matrix 𝑃𝜎 is called the sign of the permutation 𝜎: sgn(𝜎) ≔ det(𝑃𝜎). In ...
[14]
On directional scaling matrices in dimension d=2 - ScienceDirect.com
... is given by the product of a parabolic scaling matrix (1.1) and a shear matrix (1.2) on Z d . Shear matrices on Z d are unimodular matrices ( det S W = ± 1 ).
[15]
[PDF] arXiv:2302.02883v1 [math.GT] 6 Feb 2023
Feb 6, 2023 · The group SL(2,Z) is generated by the matrices s = (. 0 −1. 1 0 )and t = (. 1 1. 0 1 ) . The usual presentation of SL(2,Z) in the generators s ...
[16]
[PDF] Character formulas and descents for the hyperoctahedral group - arXiv
Jan 24, 2017 · The hyperoctahedral group Bn consists of all signed permutations of length n, meaning bijective maps w : Ωn → Ωn such that w(a) = b ⇒ w(¯a)= ...
[17]
[PDF] Square-free Discriminants of Matrices and the Generalized Spectral ...
Aug 3, 2016 · Recall that an n by n matrix U with integer entries is called unimodular if det(U) = ±1. ... signed permutation matrices. The general situation ...<|control11|><|separator|>
[18]
Integral Boundary Points of Convex Polyhedra - SpringerLink
Integral Boundary Points of Convex Polyhedra. Chapter; First Online: 01 January 2009. pp 49–76; Cite this chapter. Download book PDF ... Hoffman, A.J., Kruskal, ...
[19]
[PDF] INTEGRAL SOLUTIONS OF LINEAR COMPLEMENTARITY ...
THEOREM 5 (HOFFMAN AND KRUSKAL 1956). For A √ Z X1Y , the following are equivalent. (a) A is totally unimodular. (b) For every b √ Z X , the polyhedron {x ...
[20]
[PDF] Unimodularity
Definition A matrix is totally unimodular if each square submatrix has determinant equal to −1,0 or 1 . Totally unimodualar is a subclass of unimodular. Page 2 ...
[21]
[PDF] Totally Unimodular Stochastic Programs
Aug 3, 2006 · A Generalization of Total Unimodularity. Theorem 1 (Ghouila-Houri 1962) An m × n (0,±1) matrix A is TU iff for every J ⊆ {1,...,n} there ...<|control11|><|separator|>
[22]
[PDF] Networks and Combinatorial Optimization
Theorem 5.16 (Ghouila-Houri 1962). Let A ∈ Zm×n. Then the following is equiv- alent: (A) A is totally unimodular. (B) herdisc(A) ≤ 1. Page 53. 5.6. THE ...<|control11|><|separator|>
[23]
[PDF] Bicolorings and Equitable Bicolorings of Matrices - andrew.cmu.ed
Sep 15, 2001 · Ghouila-Houri [9] showed that a 0;±1 matrix is totally unimodular if and only if every submatrix of A has an equitable bicoloring. entries.<|control11|><|separator|>
[24]
[PDF] arXiv:1609.03537v2 [cs.GT] 17 Apr 2021
Apr 17, 2021 · Every binary matrix with the consecutive ones property is totally unimodular. We remark that by a celebrated result of Seymour (1980), it is ...
[25]
[PDF] Totally Unimodular Matrices - NC State ISE
Definition: An integral matrix A is totally unimodular(TUM) if every square nonsingular submatrix of A is UM. Observation: If A is TUM, then aij ∈ {−1,0,1}. S. ...
[26]
[PDF] Combinatorial Optimization Spring Term 2015 Rico Zenklusen
This shows that the criterion of Ghouila and Houri holds for the matrix A, implying that A is totally unimodular. Combining Theorem 5 and Theorem 3, we obtain ...
[27]
[PDF] Integral Boundary Points of Convex Polyhedra - SciSpace
(a) Independently, Alan and Joe discovered this easy theorem: if the “right hand side” consists of integers, and if the matrix is “totally unimodular”, then the ...<|control11|><|separator|>
[28]
Total Unimodularity of Matrices - SIAM.org
Feb 17, 2012 · 2. Alain Ghouila-Houri, Caractérisation des matrices totalement unimodulaires, C. R. Acad. Sci. Paris, 254 (1962), 1192–1194.
[29]
[PDF] Geometry_of_Numbers-Cassels.pdf
Lattices. 1.1. Introduction. In this chapter we introduce the most important concept in the geometry of numbers, that of a lattice, and develop some of its ...
[30]
[PDF] Introduction to Louis Michel's lattice geometry through group action ...
four crystal systems in dimension two, seven crystal systems in dimension 3, ... classification of lattices and crystals and it is important to find the most ...<|control11|><|separator|>
[31]
[PDF] SMITH NORMAL FORM IN COMBINATORICS 1. Introduction Let A ...
This paper surveys some combinatorial aspects of Smith normal form, and more generally, diagonal form. The discussion includes general algebraic properties and.
[32]
[PDF] The General Linear Group
Feb 18, 2005 · We define the special linear group, SLn(F), to be the kernel of this homomorphism. Put another way, SLn(F) = {M ∈ GLn(F) | det(M)=1} ...
[33]
[PDF] arXiv:2306.13555v2 [math.GT] 16 Apr 2024
Apr 16, 2024 · By the definition, SL(n; Z) and Γ2(n) are index 2 subgroups of GL(n; Z) and ˆΓ2(n), respectively, and Γd(n)=ˆΓd(n) for d ≥ 3. Here is an outline ...
[34]
[PDF] ON SL n. ITS GENERATORS AND RELATIONS. 1. R-modules Let R ...
Theorem 3.2. The group SLn(Z) is generated by elementary matrices eij, with i 6= j. We have n2 − n generators in all.
[35]
[PDF] Solution of the congruence subgroup problem for SLn (n 3) and ...
Congruence Subgroup Problem : Is every subgroup of finite index in F a congruence subgroup? We shall present here a complete solution of this problem. While the ...<|control11|><|separator|>
[36]
[PDF] sl2(z) - keith conrad
It is the most basic example of a discrete nonabelian group. Two particular. elements in SL2(Z) are. S = 0 −1 1 0 , T = 1 1 0 1 . The matrix S has order 4 (S2 ...<|control11|><|separator|>
[37]
4.5 The adjoint of a matrix and Cramer's rule
Integral matrices with integral inverses. If A A is a square matrix with integer entries, then A−1 A − 1 has all integer entries if and only if detA=±1.
[38]
Unimodular equivalence of graphs - ScienceDirect.com
Viewed as integer matrices, the Smith normal form of L(G) is complicated, but the Smith normal form of K(G), for connected graphs, is always I n − ...<|separator|>
[39]
[PDF] Lattices and Hermite normal form - EPFL
Since the elementary column operations are actually unimodular transformations of a matrix, the group generated by the columns of the matrix is invariant under ...
[40]
[PDF] Algebraically Doubly Stochastic Matrices Over Principal Ideal Domains
A column vector α ∈ Rn is called unimodular if there exists β ∈ Rn such that αT β = 1. The set of all n dimensional unimodular vectors over R will be denoted Um ...