Le Monde puzzle [29]

Although I am not receiving Le Monde magazine by mail any longer (maybe a consequence of highly critical posts?!), I bought it at a newsagent last Saturday and found a fairly easy mathematical puzzle. Or is it that easy? The question is to decide about the unicity of the solution to the equation

$\left[\begin{matrix} 1 &0 &1 &0 &\ldots &0 &0\\ 0 &1 &0 &1 &\ldots &0 &0\\ 0 &0 &1 &0 &\ldots &0 &0\\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 1 &0 &0 &0 &\ldots &1 &0\\ 0 &1 &0 &0 &\ldots &0 &1\end{matrix}\right]\, \mathbf{x} = \mathbf{y}$

when the matrix is (p,p). When p=9,10,11, the matrix is invertible, so there is no problem. But, looking at p=12, it is no longer invertible! When running a quick check like

for (p in 3:30){ A=diag(p) A[(1:p)+p*(((1:p)+1)%%(p))]=1 print(p) b=try(solve(A))}

we actually spot that p=4,8,12,16,20,24,28,…, i.e. all multiples of 4, lead to a non-invertible matrix. It is easy to see why for the (4,4) matrix

$\mathbf{A}_4 = \left[\begin{matrix} 1 &0 &1 &0\\ 0 &1 &0 &1\\ 1 &0 &1 &0\\ 0 &1 &0 &1\end{matrix}\right]$

since the first and second lines are repeated. The (8,8) matrix is equivalent to the bloc matrix

$\left[\begin{matrix} \mathbf{A}_4 & \mathbf{O}\\ \mathbf{B} &\mathbf{I_4}\end{matrix}\right],$

hence with the same determinant as $\mathbf{A}_4$ … In the general case, the determinant of the matrix is a circular determinant. Because most entries (but two) are zero, the determinant can easily be written as

$\prod_{j=0}^{p-1} \left\{1 + e^{\iota 4\pi j/p}\right\},$

where ι is the basic complex number. Therefore, if, and only if, p is a multiple of 4, j in the above product can take the value n/4, leading to a zero in the product… I can see why this makes a good puzzle, because this case of the multiples of 4 is quite counterintuitive!

This entry was posted on July 29, 2010 at 12:06 am and is filed under Books with tags block matrix, Le Monde, mathematical puzzle. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Xi'an's Og