Problem of the Month (September 1999)
In linear algebra, a square matrix has an equal number of rows and columns. This month, we use a different definition. A matrix is called square if each each entry is a digit, and reading across each row and down each column gives a square number. For example,
is a square matrix since 841, 196, 81, 49, and 16 are all square integers. Leading zeroes are not allowed. Not all the squares produced have to be different.
How many square m x n matrices are there? Are there square matrices of all sizes? Are there infinitely many? What is the largest square matrix you can find?
ANSWERS
Ulrich Schimke found all of the matrices below, though his program had a bug in it the first time around. He found 1584 square matrices in all. He proved that the second-to-last digit in a 1 × n square matrix is a 4. He also gives a heuristic probability argument why there are only finitely many 1 × n square matrices.
Andrew Bayly found most of the matrices below. He also noted that the search is simplified somewhat by the fact that squares only end in 0, 1, 4, 5, 6, or 9. He also found several square matrices with leading zeroes.
Joseph DeVincentis found the 1 × n and 2 × n square matrices up to n=5, and all the 3 × 3 ones. He also gave an efficient algorithm to find 2 × n matrices, using the fact that the top row completely determines the bottom row.
Brendan Owen claims that there are no square 2 × 10 matrices. All the others gave some sizes with no square matrices (like 4 × 2).
Bayly and Schimke noted that any of the 1 × n square matrices of odd length can be turned into an n x n square matrix by adding lots of zeroes in the bottom right hand corner. The largest known square matrix (21 × 21) is of this form, with first row and column 444411911999914911441 and all the rest zeroes.
The 1 × n square matrices are squares where every digit is a non-zero square. This sequence: 1, 4, 9, 49, 144, 441, 1444, 11449, 44944, 991494144, 4914991449, 149991994944, 9141411449911441, 199499144494999441, 9914419419914449449, 444411911999914911441,
419994999149149944149149944191494441 (the last one known) is sequence A006716 of the
Encyclopedia of Integer Sequences.
The 2 × n matrices found so far are:
The 3 × n matrices found so far are:
The 4 × n matrices found so far are:
|
|
|
|
|
|
|
| 5 | 3 | 3 | 1 | 4 | 8 | 1 |
| 4 | 6 | 0 | 5 | 3 | 1 | 6 |
| 7 | 0 | 2 | 2 | 5 | 0 | 0 |
| 6 | 0 | 5 | 1 | 6 | 0 | 0 |
|
There are too many 5 × 5's and 6 × 6's to list, but here are the 5 × 6 square matrices:
| 1 | 9 | 1 | 8 | 4 | 4 |
| 1 | 4 | 4 | 4 | 0 | 0 |
| 6 | 2 | 4 | 1 | 0 | 0 |
| 6 | 4 | 0 | 0 | 0 | 0 |
| 4 | 9 | 0 | 0 | 0 | 0 |
|
| 2 | 8 | 9 | 4 | 4 | 4 |
| 9 | 6 | 0 | 4 | 0 | 0 |
| 9 | 4 | 0 | 9 | 0 | 0 |
| 2 | 3 | 0 | 4 | 0 | 0 |
| 9 | 6 | 0 | 4 | 0 | 0 |
|
| 3 | 8 | 5 | 6 | 4 | 1 |
| 6 | 2 | 8 | 8 | 4 | 9 |
| 4 | 9 | 5 | 6 | 1 | 6 |
| 8 | 4 | 6 | 4 | 0 | 0 |
| 1 | 4 | 4 | 4 | 0 | 0 |
|
All of the n × n square matrices found so far are symmetric about the main diagonal. Are there any that are not symmetric? There answer is yes if we allow leading zeroes, such as this one found by Andrew Bayly:
He and Ulrich Schimke also found this 5 × 5 square matrix with the amazing properties that the diagonals are also squares, and all the squares are palindromes:
| 1 | 4 | 6 | 4 | 1 | | 4 | 4 | 9 | 4 | 4 |
| 6 | 9 | 6 | 9 | 6 | | 4 | 4 | 9 | 4 | 4 |
| 1 | 4 | 6 | 4 | 1 |
|
Schimke defined two square matrices to be twins if they differ in only one entry. He found the 4 pairs of twins below, plus 6 larger pairs. Are there any more?
|
|
|
|
| 1 | 9 | 5 | 3 | 6 | 4 |
| 9 | 8 | 6 | 0 | 4 | 9 |
| 5 | 6 | 1 | 0 | 0 | 1 |
| 3 | 0 | 0 | 3 | 0 | 4 |
| 6 | 4 | 0 | 0 | 0 | 0 |
| 4 | 9 | 1 | 4 | 0 | 1 |
|
| 1 | 9 | 5 | 3 | 6 | 4 |
| 9 | 8 | 6 | 0 | 4 | 9 |
| 5 | 6 | 4 | 0 | 0 | 1 |
| 3 | 0 | 0 | 3 | 0 | 4 |
| 6 | 4 | 0 | 0 | 0 | 0 |
| 4 | 9 | 1 | 4 | 0 | 1 |
|
| 1 | 6 | 7 | 2 | 8 | 1 |
| 6 | 0 | 0 | 6 | 2 | 5 |
| 7 | 0 | 2 | 2 | 4 | 4 |
| 2 | 6 | 2 | 1 | 4 | 4 |
| 8 | 2 | 4 | 4 | 6 | 4 |
| 1 | 5 | 4 | 4 | 4 | 9 |
|
| 1 | 6 | 7 | 2 | 8 | 1 |
| 6 | 8 | 0 | 6 | 2 | 5 |
| 7 | 0 | 2 | 2 | 4 | 4 |
| 2 | 6 | 2 | 1 | 4 | 4 |
| 8 | 2 | 4 | 4 | 6 | 4 |
| 1 | 5 | 4 | 4 | 4 | 9 |
|
Here are the number of different square matrices of different sizes:
Number of m × n Square Matrices
| m \ n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
| 11 | 12 |
|---|
| 1 | 3 | 1 | 2 | 1 | 2 | 0 | 0 | 0 | 1
| 1 | 0 | 1 |
|---|
| 2 | 1 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
|---|
| 3 | 2 | 1 | 13 | 0 | 3 | 1 | 2 | 0 | 0 |
|---|
| 4 | 1 | 0 | 0 | 14 | 1 | 0 | 1 |
|---|
| 5 | 2 | 1 | 3 | 1 | 76 | 3 |
|---|
| 6 | 0 | 0 | 1 | 0 | 3 | 108 |
|---|
In addition, Ulrich Schimke found that there are 459 symmetric 7 × 7 square matrices, and 844 symmetric 8 × 8 square matrices. No one knows if there are non-symmetric matrices of these sizes.
If you can extend any of these results, please
e-mail me.
Click here to go back to Math Magic. Last updated 10/5/99.