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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 10, 2012 at 1:03
  • $\begingroup$ @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)? $\endgroup$
    – Hooked
    Commented Aug 10, 2012 at 1:04
  • 2
    $\begingroup$ 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). $\endgroup$
    – J. M. ain't a mathematician
    Commented Aug 10, 2012 at 1:09
  • 1
    $\begingroup$ Have a look at the Pascal matrices as well. $\endgroup$
    – J. M. ain't a mathematician
    Commented Aug 10, 2012 at 1:20
  • 1
    $\begingroup$ You could generate polynomials with non-zero roots, and consider them the characteristic polynomial of a matrix. $\endgroup$
    – Emily
    Commented Aug 10, 2012 at 1:32

2 Answers 2

Reset to default
4
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented Aug 10, 2015 at 23:28

You must log in to answer this question.

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