# Solution of Magic Matrix

The easiest solution to this problem is based on observations.

```1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
```

Each individual cell makes up a magic submatrix by itself. There are 256 such submatrices. Now try to change every other value into a 2, in a chessboard-like pattern:

```1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
```

In this solution, we have fewer 1×1 submatrices, but there is the advantage that any value of 1 can be extended in 4 directions, creating multiple 1×2 and 2×1 submatrices. This approach results in 608 magic submatrices, which is considerably closer to our target.

A natural step is to add larger values. For instance, we can recreate the following 4×4 pattern, resulting in 712 submatrices:

```1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
```

A better solution is to use the following pattern instead, where each line/column contains a permutation of [1, 2, 3, 4]:

```1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1
```

This generates 832 magic submatrices:

• 64 submatrices of size 1×1
• 64 submatrices of size 1×2
• 56 submatrices of size 1×3
• 56 submatrices of size 3×1
• 176 submatrices of size 2×2
• 208 submatrices of size 1×4
• 208 submatrices of size 4×1
Questions?