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
    A random matrix is invertible with high probability, so just choose the entries randomly. Alternately, choose an upper-triangular matrix with nonzero diagonal entries. These are a little easier to invert than a general matrix but you'll still learn something from actually doing it.2012-08-10
  • 0
    @QiaochuYuan while that may be true, I want to be 100% _positive_ that the rows are linearly independent. I guess I'm also interested in the problem itself, what functions generate matrices in $GL(\mathbb{Z},N)$ (did I say that correctly)?2012-08-10
  • 2
    The matrix with entries $a_{j,k}=\min(j,k)$ is symmetric and invertible. If you really want a guaranteed nonsingular matrix with integer entries, then multiply a lower triangular matrix and an upper triangular matrix, both having nonzero diagonal entries (as Qiaochu alludes to).2012-08-10
  • 1
    Have a look at the [Pascal matrices](http://en.wikipedia.org/wiki/Pascal_matrix) as well.2012-08-10
  • 1
    You could generate polynomials with non-zero roots, and consider them the characteristic polynomial of a matrix.2012-08-10
  • 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