Matrix Attack

Question

Let $A = (a_{ij})$ be a $7 	imes 7$ matrix of integers satisfying:

• Column-permutation condition: Each column contains the numbers $1,2,\dots,7$ exactly once.

• Symmetry condition: $a_{ij} = a_{ji}$ for all $i,j$.

What is the probability that the main diagonal entries $a_{11}, a_{22}, \dots, a_{77}$ also form a permutation of $1,2,\dots,7$; that is, the numbers $1$ through $7$ appear exactly once on the main diagonal?

QuantSoc · Accepted Answer

We show that under the given conditions, the diagonal entries must always form a permutation of $1,2,\dots,7$. Hence, the probability is $1$.

For any fixed number $k \in \{1,2,\dots,7\}$:

- Since each column is a permutation of $1,2,\dots,7$, the number $k$ appears exactly once in every column.
- Therefore, throughout the entire matrix, $k$ appears exactly $7$ times.

Now consider off-diagonal entries.

Because the matrix is symmetric,

$$
a_{ij} = a_{ji}
$$

whenever $i 
e j$, every off-diagonal occurrence of $k$ appears in pairs. Hence, the number of off-diagonal appearances of $k$ is even.

Let $d_k$ denote the number of times $k$ appears on the main diagonal. Then,

$$
(	ext{off-diagonal appearances}) + d_k = 7
$$

Since the off-diagonal count is even and $7$ is odd, it follows that $d_k$ must be odd.

The diagonal contains exactly $7$ entries total, and there are $7$ distinct symbols. Each symbol must appear a positive odd number of times on the diagonal. The only possibility is:

$$
d_k = 1
$$

for every $k \in \{1,2,\dots,7\}$.

Therefore, every number from $1$ through $7$ appears exactly once on the main diagonal, meaning the diagonal is always a permutation of $1,2,\dots,7$.

Hence, the required probability is:

$$
\boxed{1}
$$