Algebraic proof of a trig matrix identity?
I'll put the question first, and then the background, because I'm not sure that the background is necessary to answer the question:
I have a geometric proof, but is there an elegant algebraic proof that $$ \left[ \begin{matrix}-1 & 1 + \cos\frac{\pi}{2n} \\ -2 & 1 + 2\cos\frac{\pi}{2n}\end{matrix} \right] ^n \left[ \begin{matrix}0 \\ 1\end{matrix} \right] = \left[ \begin{matrix}\cot \frac{\pi}{4n} \\ \cot \frac{\pi}{4n}\end{matrix} \right]$$
Background:
This is motivated by the latest maths puzzle from Spanish newspaper El País (problem statement there in Spanish, obviously). NB the deadline for submitting solutions to win the prize has passed, so don't worry about cheating. The relevant part of the problem is this:
We have two straight lines (in Euclidean geometry) and we wish to draw a zigzag between them. We start at the intersection point and draw a straight line segment of length $r$ along one of the lines (which we shall call the "horizontal line"). We then draw a straight line segment of length $r$ from the end-point to the other ("non-horizontal") line. We alternate between the two with straight line segments of the same length, without overlapping or doubling back. The 20th such line segment is perpendicular to the horizontal line. What is the angle between the lines?
There's a simple geometric solution (which I shan't state here, in case anyone wants to solve it himself - although I expect that an answer may include spoilers, so if you do want to solve it yourself, look away now), but before finding it I went down an algebraic approach which led me to an equation involving a matrix similar to the one above raised to the 10th power. Basically the equation above is the generalisation to the case with $2n$ line segments and the answer (derived from the geometric proof) substituted for the unknown angle.
The question is motivated by little more than curiosity, because I already have a proof. I've tried to prove it myself, but the best I've got so far is a messy expression in terms of some matrices whose powers do have a relatively nice closed form.
Filling in some gaps: if the lines intersect at the origin, the horizontal line is along the x-axis, the non-horizontal line is in the first quadrant, and the angle between the lines is $\alpha$, then the points are $P_{2n} = (x_{2n}, x_{2n} \tan \alpha)$ and $P_{2n+1} = (x_{2n+1}, 0)$. Given that the distance between each pair of consecutive points is $r$ we find that $x_{2n}$ and $x_{2n+2}$ are the two roots of $$(z - x_{2n+1})^2 + z^2 \tan^2 \alpha = r^2$$, and we can use the properties of the quadratic equation to get $$x_{2n+2} = \frac{2}{1 + \tan^2 \alpha}x_{2n+1} - x_{2n}$$ By using the symmetry of the triangle formed by $P_{2n+1}$, $P_{2n+2}$, $P_{2n+3}$, we get $$x_{2n+3} = 2x_{2n+2} - x_{2n+1}$$ Putting this all together we can get a recurrence which leads to an expression for $(x_{2n}, x_{2n+1})$ in terms of the nth power of a matrix applied to $(x_{0} = 0, x_{1} = 1)$. Putting any more details risks spoiling the value of $\alpha$. The RHS of the original equation comes from observing that if the $(2n)^{th}$ line segment is perpendicular to the horizontal line, $x_{2n-1} = x_{2n} = x_{2n+1}$ and $\tan \alpha = r / x_{2n}$.
The furthest I've got so far with the matrix is to split it out as $$\left( \cos\frac{\pi}{2n} \left[ \begin{matrix}0 & 1 \\ 0 & 2\end{matrix} \right] + \left[ \begin{matrix}-1 & 1 \\ -2 & 1\end{matrix} \right] \right)^n = \sum_{k=0}^{n} \left( \begin{matrix}n \\ k\end{matrix} \right) \cos^k\frac{\pi}{2n} \left[ \begin{matrix}0 & 1 \\ 0 & 2\end{matrix} \right]^k \left[ \begin{matrix}-1 & 1 \\ -2 & 1\end{matrix} \right]^{n-k} $$
where both of the matrix powers on the RHS have closed forms - the markup here doesn't seem to like the URLs and I've taken too long to write this up and need to run, but http://www.wolframalpha.com/input/?i=[[0,1],[0,2]]^k and http://www.wolframalpha.com/input/?i=[[-1,1],[-2,1]]^(r-k)
Solution 1:
You may calculate the eigenvalues of the matrix on the left hand side (which is exponentiated to the $n$-th power) which are simply $$\lambda_\pm = + \exp(\pm i\pi / 2n)$$ So the matrix $A$ is written as $A=CDC^{-1}$ where $D={\rm diag}(\lambda_+,\lambda_-)$. The corresponding eigenvectors are $$ (\frac{1}{2}(1 +\exp(\pm i\pi/2n),1)^T $$ which are written as columns of $C$, in the order "plus minus" again. Given the form of your vector $(0,1)^T$ you added, only the second column of $C^{-1}$ is important. It is $$ \mp\frac{1}{2\sin (\pi/2n)} (1 + \exp(\mp \pi i/2n)) $$ well, I mean $(n_{1},n_{2})^T$ where $n_{1,2}$ are the numbers above with the signs "upper one, lower one".
Clearly, $D^n$ is just ${\rm diag}(i,-i)$ because $\exp(i\pi /2)=i$ and so on. And I hope that the rest of $C D C^{-1} v$ is already easily calculated. Note that we had $1/\sin(\pi/2n)$ over there which is $2\sin(\pi/4n)\cos(\pi/4n)$ and the cosine cancels, leaving the sign which combines to the cotangent after some work.
Solution 2:
[moved from comment to answer] Let $\alpha=\pi/2n$ and let's call Peter's 2x2 matrix $$ A=\left(\begin{array}{rr}-1&1+\cos\alpha\\-2&1+2\cos\alpha\end{array}\right). $$ Luboš's answer tells us that the eigenvalues of $A$ are $e^{\pm i\alpha}$, so we expect the matrix $A$ to be similar to the rotation matrix $$ R=\left(\begin{array}{rr}\cos\alpha&\sin\alpha\\-\sin\alpha&\cos\alpha\end{array}\right). $$ We want to find a $2\times2$ matrix $P$ such that $PA=RP$. This is a homogeneous linear system in the unknown entries of $P$. As $R$ commutes with all the rotation matrices, we are at liberty to multiply $P$ from the left with one. Therefore we can assume that (for example) the bottom left entry of $P$ is equal to zero. The resulting system is not hard to solve, and let's pick among the solutions $$ P=\left(\begin{array}{rc}2&-1-\cos\alpha\\0&\sin\alpha\end{array}\right). $$ Then $A=P^{-1}RP$, so $A^n=P^{-1}R^nP$. Here we benefit from the fact that $$ R^n=\left(\begin{array}{rr}\cos n\alpha&\sin n\alpha\\-\sin n\alpha&\cos n\alpha\end{array}\right)=\left(\begin{array}{rr}0&1\\-1&0\end{array}\right). $$ Therefore $$ A^n\left(\begin{array}{r}1\\0\end{array}\right)=P^{-1}\left(\begin{array}{rr}0&1\\-1&0\end{array}\right)\left(\begin{array}{c}-1-\cos\alpha\\\sin\alpha\end{array}\right)= \frac{1}{\sin\alpha}\left(\begin{array}{r}1+\cos\alpha\\1+\cos\alpha\end{array}\right). $$ The identities $\sin\alpha=2\sin(\alpha/2)\cos(\alpha/2)$ and $1+\cos\alpha=2\cos^2(\alpha/2)$ then give Peter's claim as now $(1+\cos\alpha)/\sin\alpha=\cot(\alpha/2)=\cot(\pi/4n).$