7
$\begingroup$

Clearly the $1 \times 1$ and the $2 \times 2$ matrices $(1)$ and $\begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}$ are invertible. I am wondering about the following: if I take any matrix that has in the first line $(1 \ 2 \ \dots \ n)$ and in each other line a different permutation of the numbers $\{1, \dots,n\}$, will it always be invertible?

I think this is wrong for higher $n$; it might have to do with the fact that we get more permutations than we can fit in the rows and with the Leibniz formula. But still, it works with all (or most) $3 \times 3$ cases, so I am really getting curious.

If it turns out that this does not work, I would still be interested in knowing if there is at least one way of doing it that works (for every $n$) and if it is relevant that we have chosen $\{1,\dots,n\}$ and not any other (real, different, positive) entries.

Edit:

As pointed out in the comments and in user1551's answer, this is not always the case, not even when in each column and in each row each element appears exactly once. I would still like to know why all the $3 \times 3$ matrices (of this kind) are always invertible and, above all, why the "shift matrix" mentioned in Hw Chu's comment is indeed always invertible (and whether there are other procedures that always work).

$\endgroup$
4
  • 3
    $\begingroup$ Say, if $n = 6$, there is one easy way to generate a non-invertible matrix: For each line you start with $(1 2 3)$ and end with a different permutation of $\{4,5,6\}$. On the other hand, the "shifting matrix" given by assembling $(1 2 \cdots n)$, $(2 3 \cdots n 1)$, ..., $(n 1 2 \cdots (n-1))$ must be invertible. $\endgroup$
    – Hw Chu
    Apr 10 '18 at 18:52
  • $\begingroup$ @HwChu Could you please explain to me why the "shifting matrix" is invertible? I have found examples of Sudoku matrices that are not invertible, even though each line and row contains all the integers from $1$ to $9$ exactly once, so there must be something more subtle I am missing. $\endgroup$
    – 57Jimmy
    Apr 11 '18 at 9:37
  • 2
    $\begingroup$ That so-called "shift matrix" is commonly known as a circulant matrix, whose determinant admits an explicit formula. In your case, it suffices to show that $\omega=\exp(2\pi ij/n)$ is not a root of $1+2x+3x^2+\ldots+nx^n$ for $j=0,1,\ldots,n-1$. $\endgroup$
    – user1551
    Apr 11 '18 at 12:41
  • $\begingroup$ Inverse of Latin Square, maybe useful. In fact, you are interested to check how an $n \times n$ Latin Square $L$ is invertible when $L$ is constructed with elements $\{1, \dots,n\}$. $\endgroup$
    – Amin235
    Apr 11 '18 at 14:53
4
$\begingroup$

It isn't always invertible. E.g. when $$ A=\pmatrix{1&2&3&4\\ 1&2&4&3\\1&3&2&4\\ 1&3&4&2}, $$ the sum of the last three columns of $A$ is a multiple of the first column.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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