I am trying to find an elementary proof that if $\phi$ is a linear map from $\mathbb{Z}^n\rightarrow \mathbb{Z}^m$ represented by an $m \times n$ matrix $A$, then the map is surjective iff the gcd of the determinants of all the $m\times m$ minors of $A$ is $1$.

I know that for there to be surjectivity between $\mathbb{Z}^n$ and $\mathbb{Z}^m$ $n$ must be greater than or equal to $ m$ and for there to even be $m \times m$ minors $n$ again must be greater than or equal to $ m$, so I just assume this throughout.

I sort of have one direction $\Leftarrow$

i) Greatest Common Divisor =1 implies surjectivity: First observe that the if $ | \mathbb{Z}^m/ Im(M)| < \infty$ then $|\det M| = | \mathbb{Z}^m/ Im(M) |$ otherwise $\det(M) = 0$ where $M$ is an $m\times m$ matrix. We can consider the $n$ columns of $A$ as column vectors $v_1, v_2, \ldots, v_n$. These $n$ column vectors live in $\mathbb{Z}^m$. Let $S'' = \{ v_i\}$ and then let $S'$ be subsets of $S''$ of cardinality $m$ and lastly let $S$ be the elements of $S'$ such that when the $m$ $v_i$ vectors are considered as $m\times m$ matrices, the determinant is not zero, thus $S$ consists of all $m\times m$ minors of $A$ with non-zero determinant (we ignore zeroes since they do not affect gcd). For each $s\in S$ define a map $i_s: \mathbb{Z}^m \rightarrow \mathbb{Z}^n$ that maps the standard basis of $\mathbb{Z}^m$ to the basis elements $e_k \mathbb{Z}^n$ such that $v_k \in s$. That is, $\phi \circ i_s$ gives the matrix created by the column vectors of $s$. Let $\Lambda$ be the lattice Im$\phi \supset \sum_{s\in S}$ Im $\phi\circ i_s =\sum_{s \in S} \Lambda_s$. Thus $\forall s \in S$, $\Lambda_s \subset \Lambda \subset \mathbb{Z}^m$. Thinking in terms of group theory, we have that $\Lambda$ is a subgroup of $\mathbb{Z}^m$ and all the $\Lambda_s$ are subgroups of $\Lambda$. Thus by Lagrange's Theorem, we have $|\mathbb{Z}/\Lambda| \Big\vert |\mathbb{Z}^m/\Lambda_s|$ Since $|\mathbb{Z}^m/\Lambda_s|$ are the determininants of the $m\times m$ minors and the definition of the common divisor of several integers is the greatest positive integer dividing all of them. Thus by hypothesis $|\mathbb{Z}/\Lambda| \leq 1$ and so $|\mathbb{Z}/\Lambda| =1$ and we have that Im$A=\Lambda = \mathbb{Z}^m$ so the map is surjective.

I was hoping to get a more elementary proof that doesn't rely on the observation that the if $ | \mathbb{Z}^m/ Im(M)| < \infty$ then $|\det M| = | \mathbb{Z}^m/ Im(M) |$ otherwise $\det(M) = 0$ where $M$ is an $m\times m$ matrix or normal forms.


  • $\begingroup$ I am hoping for something just uses properties of determinants and the definition of surjective that the columns of the matrix generated all of $\mathbb{Z}^m$. $\endgroup$ – Steven-Owen Apr 16 '12 at 23:02

Let $R$ be a commutative ring, and $f : R^n \to R^m$ be a homomorphism of $R$-modules with corresponding $m \times n$ matrix $A$ over $R$. Let $Y_1,\dotsc,Y_v$ be the $m \times m$ submatrices of $A$. Then $f$ is surjective iff the $\mathrm{det}(Y_1),\dotsc,\mathrm{det}(Y_v)$ generate the unit ideal of $R$.

Proof (which I learned from Darij Grinberg): Assume that $f$ is surjective. Then there is some $n \times m$ matrix $B$ with $AB=1_m$. Let $Z_1,\dotsc,Z_v$ denote the $m \times m$ submatrices of $B$. Then the Cauchy-Binet formula (which has a nice graph theoretic proof) implies $1=\mathrm{det}(AB)=\sum_{s=1}^{v} \mathrm{det}(Z_s) \mathrm{det}(Y_s)$.

Conversely, assume $\sum_s \lambda_s \mathrm{det}(Y_s)=1$ for some $\lambda_s \in R$. Let $B_s$ denote the $n \times m$ matrix, which is built up out of $\mathrm{adj}(Y_s)$ and with zero columns which were deleted in $A \mapsto Y_s$. Let $B = \sum_{s=1}^{v} \lambda_s B_s$. Then we have

$$AB = \sum_s \lambda_s A B_s = \sum_s \lambda_s Y_s \mathrm{adj}(Y_s) = \sum_s \lambda_s \mathrm{det}(Y_s) 1 = 1.$$

Remark: One can show that $f$ is injective iff $(\mathrm{det}(Y_1),\dotsc,\mathrm{det}(Y_s))$ is a regular ideal.

  • $\begingroup$ So for the conclusion of the first you used a generalization of Bezout's identity? I am not really sure I understand your proof in the other direction. $\endgroup$ – Steven-Owen Apr 17 '12 at 20:41
  • $\begingroup$ I don't need Bezout. Please ask specific questions about the proof, then I can answer them. Also observe that the statement holds in every commutative ring - it doesn't matter which one. But then we have to replace "gcd = 1" with "generate unit ideal" (which is equivalent at least in Bezout rings, such as PIDs). $\endgroup$ – Martin Brandenburg Apr 18 '12 at 7:36
  • $\begingroup$ You're right you don't need the Bezout identity because you showed that there is a linear combination $\det(Y_i)$ that is equal to the unit and therefore generates the unit ideal. However, I am not sure how you got that all $\det(Z_s)$ would be in $R$ in the first place. Wouldn't it be possible the entries of the right inverse live in the field of fractions of $R$ rather than $R$. Or is it when you take the determinant they are back in $R$? $\endgroup$ – Steven-Owen Apr 18 '12 at 15:36
  • $\begingroup$ We don't leave $R$ at all and we don't need inverses. $\endgroup$ – Martin Brandenburg Apr 21 '12 at 5:34
  • $\begingroup$ @MartinBrandenburg Concerning the remark: what do you mean by a vector in $R^s$ to be regular? (I guess you wanted to say that the ideal is regular, that is, contains a nonzerodivisor.) $\endgroup$ – user26857 Jan 15 '13 at 9:09

I'm not sure what kind of machinery you're willing to use. The following proof is short but sophisticated.

First, recall the three types of integer row operations:

  1. Negating a row,

  2. Switching two rows,

  3. Adding an integer multiple of one row to another.

Each of these operations corresponds to a change of basis in the codomain of $\phi$. Similarly, integer column operations correspond to a change of basis in the domain of $\phi$.

Using integer row operations and integer column operations, any integer matrix can be reduced to Smith normal form.

Now, here is the proof:

  1. Observe that the gcd of the determinants of the $m\times m$ minors is unaffected by integer row and column operations. (In particular, a type 1 column operation will negate some of the determinants, a type 2 column operation will switch certain pairs of determinants and negate others, and a type 3 column operation will add an integer multiple of certain determinants to other determinants.)

  2. Observe that being surjective is also a property not affected by row/column operations. To see this, note that row/column operations on $A$ correspond to multiplication by invertible matrices (with determinant 1) on the left/right. Assuming that $A$ is surjective you show that $B=PAQ$ is surjective too by solving $Bx=y$ with $x=Q^{-1}u$, where $u$ is a solution to $Au=P^{-1}y$.

  3. Therefore it suffices to prove the statement in the case where $A$ is in Smith normal form. Such a matrix has only one $m\times m$ minor with nonzero determinant, and this determinant is $1$ if and only if $\phi$ is onto.

  • $\begingroup$ Thank you, but alas I'm looking for something that doesn't use this diagonalizing method. $\endgroup$ – Steven-Owen Apr 16 '12 at 23:01
  • $\begingroup$ +1 for simplicity. Your post helped me prove forward direction (I haven't done backwards yet) $\endgroup$ – Pascal's Wager Mar 21 '18 at 21:06
  • $\begingroup$ It should be mentioned that surjectiveness is also unaffected by row/column operations. $\endgroup$ – Arnaud Mortier Jul 1 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.