Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Qiaochu Yuan Aug 10 '12 at 1:03
    
@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)? –  Hooked Aug 10 '12 at 1:04
1  
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). –  J. M. Aug 10 '12 at 1:09
    
Have a look at the Pascal matrices as well. –  J. M. Aug 10 '12 at 1:20
1  
You could generate polynomials with non-zero roots, and consider them the characteristic polynomial of a matrix. –  Arkamis Aug 10 '12 at 1:32
show 1 more comment

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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