2
$\begingroup$

I am a bit curious about an exercise.

I was supposed to prove that there is no matrix that has $1,2,3,4$ in each line and is symmetric. I did, by examination of all such matrices.

Now, there is a such a matrix for $1,2,3$, namely

$$\left(\begin{array}{ccc} 1&3&2\\ 3&2&1\\ 2&1&3\\ \end{array}\right)$$

How does the result generalize? Is it a odd vs even thing? Or $n \gt 4$ is always impossible?

Proofs using linear algebra are especially welcome!

$\endgroup$
  • $\begingroup$ It's unlikely there will be a "linear algebra" proof here, since there are no questions about linear equations, linear independence, vector spaces, linear transformations, etc. For any $n$ just start with any row and do a cyclic shift to the left by 1 for each row. $\endgroup$ – Morgan Rodgers May 20 at 22:44
  • $\begingroup$ @MorganRodgers, fair enougth, but strang has this tendency of linking linear algebra to everything, that makes me wonder $\endgroup$ – josinalvo May 21 at 12:58
5
$\begingroup$

On the contrary... it is possible for every $n$.

Let $A_{i,j} = i+j\pmod{n}$

By commutativity of addition it is obvious that the matrix is symmetric. Further, by fixing $i$ or fixing $j$ and letting the other range over all possible values it is clear that there is no repetition in any row or column.

$\endgroup$
5
$\begingroup$

There are 2 other ways for building such a matrix, for most dimensions.

1) Thinking to (symmetric) "latin squares" https://en.wikipedia.org/wiki/Latin_square ; here is a method : https://pdfs.semanticscholar.org/d669/4364b5650f32e84255ab0a76138c55049593.pdf

2) (connected) Thinking to Cayley tables of abelian groups (https://en.wikipedia.org/wiki/Cayley_table).

Indeed, the table of a group is known to be a latin square : (https://en.wikipedia.org/wiki/Latin_square_property). (reciprocal untrue).

If moreover, this group is commutative, it provides an answer to the question.

Let us take an example : the multiplicative group of the finite field $\mathbb{F}_p$ where $p$ is a prime number ; we can build a matrix $(p-1) \times (p-1)$ in the following way

$$A_{i,j}=i*j \ \text{mod} \ p$$

(reminds the solution of @JMoravitz !) that fulfills your condition because multiplication mod $p$ gives the set of nonzero classes $\{\overline{1},\overline{2},\cdots \overline{p-1}\}$ an abelian group structure.

$\endgroup$
1
$\begingroup$

Why can't you say?

\begin{bmatrix} 1&2&3&4\\ 2&1&4&3\\ 3&4&1&2\\ 4&3&2&1 \end{bmatrix}

or

\begin{bmatrix} 1&2&3&4\\ 2&3&4&1\\ 3&4&1&2\\ 4&1&2&3 \end{bmatrix}

This seems more like abstract algebra though, as these arrays are the Cayley tables for the two group structures of order four.

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