Luoshu: An extended discussion on the fun math question (repost)
Published:
This is simply a takeaway quiz from a course. Originally the professor looks for answers for how to fill in 9 numbers into a 3x3 matrix so that each row, column, and diagonal are all summed up to the same number, which is 15. This is an ancient problem called "Luoshu"(or 洛書 in Chinese) which comes from ancient China. In this question, the answer is not unique. However, I found some more interesting properties far beyond equal summations. So what I do is simply find out mathematical explanations for these properties including equal sum and equal square sum. Also, those properties can be extended to a larger matrix.
The original puzzle
Given a 3x3 matrix and 9 unique integers from 1 to 9, fill out the matrix such that each row, column, and diagonal are all summed up to the same number. (Hint: the same number is 15 in this case.) And this is one possible answer:
How to come up with this answer?
One way to come up with this answer is to start placing 1 to 9 diagonally from the top-left toward the right button. Whenever the next location is taken, move your target location one cell up instead. The trick is: to view the boundary of the 3x3 matrix as circular wall in all directions, and the 1 starts from the middle button.
Analysis
First of all, I found out this additional property (the column square sum property):
You may wonder: "OK…? How do I know if this is true? I need to double-check, let me calculate it first…". After your calculation, you might also be like: "It might be just a coincidence, not a big deal. And what can this property tell us?" Well, what I discovered is not just this coincidence, but the beauty behind it. To extend this additional property further in the following, I denote the answer matrix as an element-wise matrix summation result of two special matrices: the median matrix and the index matrix.
By applying the denotation back to equation (1), we will get:
or equivalently, the following:
Upon the tedious calculation of double-checking that you may want to do it, the bold section of equation (3) kinda caught my attention. Intuitively for me, this is some sort of convolution result that two sides are equal to each other. To formalize it, I define
(Don't bother thinking why. The idea of f[x] comes from the index matrix, and h[x] comes from the median matrix) I also define the circular convolution of f[x] and h[x] as g[x]:
And now, the square sums of each column in the answer matrix can be represented by g[x]. The square sum of the first column:
If you apply the same logic to the third column, to shorten the notation here, let \(\mathbf{offset} = 2^2+5^2+8^2+(-1)^2+0^2+1^2\), the result is:
By comparing equation (4) and (5), the equality of two column's square sums comes from the equality of g[0] and g[2]! The same logic applies to row square sums where you need to re-define f[x] and h[x] in the following:
I will leave the calculation as practice, and the final square sum is 101.
Extend to larger matrices
So far all the analysis may look over-complicated, while the magic of circular convolution interpretation kicks in when the size of the answer matrix grows. If we extend the original puzzle to a 5x5 matrix with 25 unique numbers 1 to 25 that you need to fill in, the answer matrix and corresponding median matrix and index matrix will look like this:
The f[x] and h[x] for 5x5 matrix are:
And you can derive the square sum of the first column:
where g[0] is:
For the fifth column, the square sum is:
This is the moment where I strongly feel I found the pattern, although I have no formalized proof at this moment, but it does apply to any NxN matrix, where N=2k+1, and k is nature number.