6
$\begingroup$

Integer matrices with determinant equal to $1$ are quite useful in many situations. Take, for example, this question. For the $2 \times 2$ case it's easy to find many such matrices, e.g.,

$$\begin{bmatrix} 2 & 3 \\ 3 & 5 \\ \end{bmatrix}$$

$$\begin{bmatrix} 4 & 3 \\ 5 & 4 \\ \end{bmatrix}$$

  • But how to construct the procedure for generation integer matrix with arbitrarily chosen dimension $n \times n$?
  • Is it a method which is as general as it is possible?
  • I'm also interested in the answer how many degrees of freedom has an integer matrix with determinant equal 1 (or other perhaps number) ? Without determinant constraint $n \times n$ matrix has of course $n^2$ degrees of freedom.. how many is lost when we constrain it with determinant?
$\endgroup$
6
  • 1
    $\begingroup$ There is a name for these, the special linear group of $n\times n$ matrices over the integers, $SL(n,\mathbb{Z})$, a group with respect to matrix multiplication. $\endgroup$
    – hardmath
    Jul 14, 2017 at 13:23
  • $\begingroup$ @hardmath is this somewhere described? all references are valuable.. $\endgroup$
    – Widawensen
    Jul 14, 2017 at 13:30
  • $\begingroup$ This 1992 paper in the Proc. of the AMS opens by describing one set of generators called transvections $T_{ij}$. To obtain a presentation of these finitely generated groups, one needs to articulate the relations satisfied by those generators, which is the topic of that paper. $\endgroup$
    – hardmath
    Jul 14, 2017 at 13:35
  • $\begingroup$ @hardmath paper maybe a little too advanced as for me but anyway thank you very much.. $\endgroup$
    – Widawensen
    Jul 14, 2017 at 13:38
  • $\begingroup$ I'll try my hand at writing up an exposition of this material for you, esp. as it bears on your interest in the "degrees of freedom" issue. $\endgroup$
    – hardmath
    Jul 14, 2017 at 13:55

3 Answers 3

5
$\begingroup$

You can just start with the identity matrix and apply transformations that don't change the determinant:

  1. Adding to column (row) another column (row) multiplied by an integer.
  2. Performing an even permutation of the columns (rows).

Hart to tell what is degrees of freedom for a discrete set. Its dimension is zero. But you can think of it a cutting all the $n^2$ dimensions that you had by one equation. So, $n^2-1$.

$\endgroup$
7
  • $\begingroup$ Give some examples how this acts... what about degrees of freedom ? $\endgroup$
    – Widawensen
    Jul 14, 2017 at 11:30
  • $\begingroup$ Could you obtain with this procedure for example $\begin{bmatrix} 2 & 3 \\ 3 & 5 \\ \end{bmatrix}$? $\endgroup$
    – Widawensen
    Jul 14, 2017 at 11:33
  • $\begingroup$ @Widawensen I would have to try. But for $2\times2$ matrices you can get all of them by mutiplying together powers of the two matrices $[[1,1],[0,1]]$ and $[[0,-1],[1,0]]$. $\endgroup$
    – user463383
    Jul 14, 2017 at 11:42
  • $\begingroup$ That's the other method (maybe to add to the answer?) it is really quite general - multiplying matrices with determinant $1$ gives really always matrix with determinant $1$ .. $\endgroup$
    – Widawensen
    Jul 14, 2017 at 11:48
  • 1
    $\begingroup$ For the claim that these generate all the $2\times 2$ cases, see this previous Question, "Generating the special linear group of 2 by 2 matrices over the integers". $\endgroup$
    – hardmath
    Jul 14, 2017 at 13:18
4
$\begingroup$

To motivate what might be said about "degrees of freedom" in the more general $n\times n$ case, let's look at the $2\times 2$ case in some detail.

One might informally say that the degrees of freedom in the special linear group $SL(2,\mathbb{Z})$ has an intuitive sense of "the number of coordinates needed to specify an instance".

This is a firmer notion when the coordinates involved are real numbers than when, as here, the coordinates are only discrete integers. The problem is related to the possibility that a pair of integers might be coded together as a single integer, so that the counting "how many coordinates are needed" becomes muddled. In the case of real numbers we are saved by imposing a requirement that any "coding" has to involve continuous functions (in a suitably restricted domain) that are continuously invertible (decoding). This prevents a pair of real numbers from being combined into a single real number.

Acknowledging that we are walking on slippery ground, let's consider a couple of "natural ways" to parameterize $SL(2,\mathbb{Z})$. The first involves making an arbitrary choice of the two diagonal entries $a,d$:

$$ \begin{bmatrix} a & b \\ c & d \end{bmatrix} $$

Since we desire that $ad - bc = 1$, we have (in order to get an element of $SL(2,\mathbb{Z})$) only to solve:

$$ bc = ad - 1 $$

Apart from the peculiar case that $ad = 1$ (which admits an infinite number of solutions $b,c$ provided at least one of them is zero), we find that there will be only finitely many $b,c$ which "factor" $ad - 1$.

This seems to say that there are (loosely speaking) two degree of freedom, since (with the two exceptions $a = d = \pm 1$) the values $a,d$ can be chosen arbitrarily and leave a finite number of additional "choices" (about the ways $ad - 1$ will factor).

On the other hand we might begin with choosing $a$ and $b$. Now the valid choices are those pairs $a,b$ which are coprime (no common divisor greater than one). Although not every pair is satisfactory in this sense, the relative fraction of coprime pairs $a,b$ in an expanding region $[-M,M]\times [-M,M]$ as $M\to \infty$ converges to $6/\pi^2$, which is roughly $61\%$.

So again it seems that choosing $a,b$ requires two degrees of freedom. Further, as $a,b$ are coprime, there exist coefficients $c,d$ such that $ad-bc=1$. Then we can introduce an additional integer coordinate $k$ because:

$$ \det \begin{bmatrix} a & b \\ c+ak & d+bk \end{bmatrix} = 1 $$

By this reckoning we would have three degrees of freedom at our disposal!

$\endgroup$
3
  • $\begingroup$ Very interesting argumentation, integer entries can lead to paradoxes? $\endgroup$
    – Widawensen
    Jul 17, 2017 at 11:59
  • $\begingroup$ Well, it reinforces @user463383's remark that it's "har[d] to tell" what degrees of freedom are for a discrete set. I don't think the results are really paradoxical. The first way gives two degrees as a lower bound (because we neglect that the number of factorizations is finite for each $a,d$ but on average grows as $a,,d$ become larger), and the second way is an upper bound (because we award two degrees of freedom for $a,b$). $\endgroup$
    – hardmath
    Jul 17, 2017 at 12:07
  • $\begingroup$ O.k. Let some kind of ambiguity remain.. maybe the nature of variety ( I'm not sure whether the word "variety" is proper here, maybe manifold?) can be generated by the determinant equation ( this would be some kind of the grid lying on this hyper-surface in 4D) $\endgroup$
    – Widawensen
    Jul 17, 2017 at 12:14
2
$\begingroup$

Say that we want to generate the integer matrix $$A=\begin{pmatrix}a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}\end{pmatrix}$$ so that $\det(A)=1$. We start by randomizing the rows $2,\dots, n$. Now a cofactor expansion in row 1 shows that the problem is equivalent to the one of finding solutions to the diophantine equation $$c_{11}a_{11}+c_{12}a_{12}+\dots+c_{1n}a_{1n} = 1$$ where $c_{11},\dots,c_{1n}$ are the cofactors of the first row of $A$. Since the rows $2,\dots,n$ have been set, the cofactors can easily be calculated. The diophantine equation is solvable if $\gcd\{c_{11},\dots,c_{1n}\}=1$ and in that case the solutions depend on $n-1$ parameters. An advantage of this method is that you can control the size of the entries of $A$.

I have developed a Python program that randomizes an integer matrix with determinant as a parameter. You can find it here: https://github.com/andis854/matrix_rdn_det.

$\endgroup$
2
  • $\begingroup$ Interesting method but how .... we can be sure that $\gcd\{c_{11},\dots,c_{1n}\}=1$ ? $\endgroup$
    – Widawensen
    Mar 3, 2023 at 10:57
  • $\begingroup$ We cannot! So in that case one has to generate new numbers for the rows $2,\dots,n$. However the likelihood of the $\gcd$ not being $1$ is low, so this is not a serious computational problem. $\endgroup$
    – andis854
    Mar 6, 2023 at 11:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .