I am looking for a proof of the following:
A square grid is filled out with symbols from some alphabet, with one symbol in each square of the grid. Each row of the grid is the same as some column (i.e. the sequence of symbols obtained from reading across any row from left to right is the same as the sequence of symbols obtained from reading (at least) one of the columns from top to bottom).
Show that every column is also the same as some row.
I am asking because I run a site which is creating an archive of Enigma puzzles that were originally published in New Scientist magazine between 1979 and 2013. Mostly I focus on programmatic solutions, but some problems need a more analytic approach.
This question is part of Enigma 1248 -https://enigmaticcode.wordpress.com/2015/03/16/enigma-1248-rows-and-columns/
Here's a sketch of a solution.
If all the rows are distinct, then it's clear that each column must be the same as some row. So, assume rows $i$ and $j$ are identical ($i\ne j$).
Now consider row $k$. It must be identical to some column, say, column $\ell$. Since rows $i$ and $j$ are identical, the $(i,\ell)$ and $(j,\ell)$ entries must be equal. Since row $k$ is identical to column $\ell$, the $(k,i)$ and $(k,j)$ entries must be equal. Since $k$ was arbitrary, columns $i$ and $j$ must be identical.
So, we have proved that if rows $i$ and $j$ are identical, then columns $i$ and $j$ are identical.
More generally, if the rows in any collection are identical, then the columns in the corresponding collection must be identical.
It follows that the number of distinct rows equals the number of distinct columns, and then that each column must be identical to some row.