6
$\begingroup$

While explaining how to invert matrices I once used this ill-fated example $A=\begin{pmatrix} 1&2&3\\4&5&6 \\7&8&9 \end{pmatrix}$ which can not be inverted ($\det(A)=0$). That got me thinking, given a matrix of size $N$, what are some good functions that map to the elements such that:

  1. The elements are integers
  2. The elements are "small" (for hand calculation)
  3. The matrix is always invertible
  4. (optional) the function has a random component, but still satisfies (3)

Let $A_{ij} = f(j + (i-1)N)$. In the example above $f(n) = n$.

  • 0
    Hooked, do you insist that the inverse also have integer entries? If so, you are talking about GL$(N,{\bf Z})$ (maybe better to call it SL$(N,{\bf Z})$). If not, not.2012-08-10

2 Answers 2

4

For very structured matrices, where you know the determinant in advance, use Vandermonde matrices. One can also disguise them a little.

If you want a random component, make the entries on the main diagonal odd, and the all the remaining entries in some row or some column even, with the rest of the entries arbitrary. Then the determinant will be odd, and in particular non-zero.

There are many variants of this idea. For example, choose entries down the main diagonal not divisible by $3$, and the remaining entries in some row or some column divisible by $3$.

3

a. The answer given by Andre Nicolas is wrong, even for 3x3 matrices. The matrix

1 2 2

a 1 1

b 1 1

has a determinant of 0 no matter what values a and b have.

...

b. I am working on writing a "cookbook" for random generation of matrices with certain properties. For the problem posted by Hooked, I generate:

  1. a lower triangular matrix L whose diagonal entries are in {+1,-1} (bonus: if the number of nonzero entries is small, then there aren't that many row operations to perform),
  2. an upper triangular matrix U whose diagonal entries are in {+1,-1}, and
  3. a random permutation matrix P.

Then A = PLU is a suitable matrix for finding the inverse by hand. Also, the determinants of P, L, and U are +1 or -1, so A has determinant +1 or -1, which means its inverse has integral entries.

  • 1
    Andre's answer can be partly salvaged by making the diagonal entries odd (or more generally non-divisible by some prime $p$), all the above-diagonal entries even (or divisible by $p$), and the below-diagonal entries arbitrary integers. Or interchange "above" and "below". And again you can pre- or post-multiply by any invertible matrix, in particular permutations.2015-08-10