Fog Creek Software
Discussion Board

the matrix reordered

There is a matrix of numbers, 1997 rows by 1997 columns. The matrix is symmetric: a value in row i, column j will equal the value in row j, column i.

Each row (and because of symmetry , each column) is a permutation of all numbers 1 through 1997; in any row, each integer from 1 through 1997 occurs exactly once.

Are the values on the main diagonal (cells in row i, column i) also such a permutation? Why or why not?

Peter Meilstrup
Friday, May 16, 2003

1 2 3
3 1 2
2 3 1

Friday, May 16, 2003

ough... wrong example. will think more

Friday, May 16, 2003

ok, nice riddle, Peter. the answer is yes, but i don't want to spoil the fun and write solution right away.

Friday, May 16, 2003

I think I have a part solution, but certainly not a proof.

If you start with a matrix that satisfies the requirements, you can transform it into any other matrix that also satisfies the requirements simply by swapping pairs of numbers. To maintain symmetry, any operation that you do on the top right part of the matrix must also be done on the bottom left of the matrix. However, any swap involving an element on the diagonal must be a swap with another element on the diagonal. So if we can show that there is one solution like this, then all solutions must be like this.

Unfortunately I haven't found a way of proving that there is one solution like this. Over to you guys....

David Clayworth
Friday, June 13, 2003

Okay, this has gone for some time, so I'll drop a hint or two.

Pay special attention to the way that I phrased the permutation requirement: Each number appears exactly once in each row.

Therefore, over the whole matrix, each number appears exactly 1997 times.

Peter Meilstrup
Monday, June 16, 2003

That 'Aha' moment.

I found a way of generating the one solution I needed to complement my answer above. It's easy. In the first row start with the numbers ordered, and in the second and subsequent you move each number one place left. That got me thinking about why the problem didn't work with an even number of rows (that's another hint if you haven't guessed it already), and suddenly I'm there.

Nice puzzle, Peter, with a nice big Aha factor.

David Clayworth
Wednesday, June 18, 2003

Indeed, the Aha factor on this one is pretty big.

I'll post the solution for the impatient.

_______ SPOILERS BELOW_______

Each whole number from 1 to 1997 appears in the matrix 1997 times.

Since the matrix is symmetric, each number can only appear an even number of times OFF the main diagonal.

Since 1997 is odd, each number must appear an odd number of times ON the main diagonal to make up the total.

The only way this can happen is for each number to appear on the diagonal exactly once--so the answer is yes. (and would have been "no" for an even-sized matrix.)

Peter Meilstrup
Tuesday, June 24, 2003

*  Recent Topics

*  Fog Creek Home