MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for guidance about the behavior of powers of a particular matrix (call it $A_n$ for $n\ge2$), which has come up in a counting problem about quantum knot mosaics (a good reference for quantum knot mosaics is here ). Here's a description of the matrix. It has $4^n$ rows and columns. Instead of a traditional diagonal matrix with its non-zero entries on the main diagonal, the non-zero entries of $A_n$ are on an ``oblique diagonal" of slope $4$, modulo the size of the matrix. More precisely, the non-zero entries occur where $\left\lfloor\frac{\text{column}}4\right\rfloor=\text{row}\text{, mod}\;4^{n-1}$. The matrix has sixteen possibly non-zero values $a_1,\ldots,a_{16}$, arranged as follows (with boxes for visual clarity):

$\begin{array}{l|lll|lll|} \text{row}\backslash\text{column}&0&4&\ldots&4^n/2&4^n/2+4&\ldots\\ \hline 0&\boxed{a_1\,a_2\,a_1\,a_2}\\ 1&&\boxed{a_1\,a_2\,a_1\,a_2}\\ \vdots&&&\ddots\\ \hline 4^n/8&&&&\boxed{a_3\,a_4\,a_3\,a_4}\\ 4^n/8+1&&&&&\boxed{a_3\,a_4\,a_3\,a_4}\\ \vdots&&&&&&\ddots\\ \hline 2\cdot4^n/8&\boxed{a_5\,a_6\,a_5\,a_6}\\ 2\cdot4^n/8+1&&\boxed{a_5\,a_6\,a_5\,a_6}\\ \vdots&&&\ddots\\ \hline 3\cdot4^n/8&&&&\boxed{a_7\,a_8\,a_7\,a_8}\\ 3\cdot4^n/8+1&&&&&\boxed{a_7\,a_8\,a_7\,a_8}\\ \vdots&&&&&&\ddots\\ \hline 4\cdot4^n/8&\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ 4\cdot4^n/8+1&&\boxed{a_{9}\,a_{10}\,a_{9}\,a_{10}}\\ \vdots&&&\ddots\\ \hline 5\cdot4^n/8&&&&\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ 5\cdot4^n/8+1&&&&&\boxed{a_{11}\,a_{12}\,a_{11}\,a_{12}}\\ \vdots&&&&&&\ddots\\ \hline 6\cdot4^n/8&\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ 6\cdot4^n/8+1&&\boxed{a_{13}\,a_{14}\,a_{13}\,a_{14}}\\ \vdots&&&\ddots\\ \hline 7\cdot4^n/8&&&&\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ 7\cdot4^n/8+1&&&&&\boxed{a_{15}\,a_{16}\,a_{15}\,a_{16}}\\ \vdots&&&&&&\ddots\\ \hline \end{array}$

Since $A_n$ has a straightforward geometrical description with non-zero entries only on a diagonal (albeit an oblique one), the following question seems reasonable:

Is there an elementary way to compute the eigenvalues of this matrix in terms of $a_1,\ldots,a_{16}$ and $n$?

I'm no expert in tensor algebra, but it seems that $A_n$ might be expressed as the tensor product of $A_2$ with $n-1$ copies of another transformation. Even an approximation of the largest eigenvalue would be useful, but it would be best to avoid the power method with the Rayleigh quotient since I'm trying to analyze the powers of the matrix in terms of the eigenvalues, not vice versa. Any insight into the computation of the eigenvalues of $A_n$ would be greatly appreciated and would go a long way in answering a question in the paper referenced above.

share|cite|improve this question
Impressive LaTeX {array}! :-) – Joseph O'Rourke Apr 5 '12 at 0:23
Well, as Donald Knuth said, TeX is intended for the creation of beautiful mathematics. – Russell May Apr 5 '12 at 12:32

I think that if you move some rows around you get a block diagonal form (this the tensor product from the previous post). Move all the rows that start in col 1 together, rows in col 5 etc. The eigenvalues etc. will be related to the eigenvalues etc. of the blocks.

share|cite|improve this answer
I agree that there's a permutation matrix P and a block diagonal matrix A' so that the oblique diagonal matrix A is PA'. However, it's not clear how to get the eigenvalues of a product, given the eigenvalues of the factors. – Russell May Apr 6 '12 at 18:44

Not a complete answer but a heuristic argument that there is little hope for a good estimation, let alone an exact solution. Take the matrix $$\pmatrix{a&b&.&.&.&.&.&.\\ .&.&a&b&.&.&.&.\\ .&.&.&.&a&b&.&.\\ .&.&.&.&.&.&a&b\\ a&b&.&.&.&.&.&.\\ .&.&a&b&.&.&.&.\\ .&.&.&.&c&d&.&.\\ .&.&.&.&.&.&c&d }$$ which is a special case of an $8\times 8$ "equivalent" (sort of) and has the characteristic polynomial $$x^3\left[x^5-(a+d)x^4+a(d-b)x^3+b(a+d)(ad-bc)x-b(ad-bc)^2\right].$$ Now, the factor in brackets is of form $x^5+px^4+qx^3+rx+s$ with linearly independant coefficients (in terms of $a,b,c,d$), i.e. a quintic in almost general form, with just the $x^2$ term missing. AFAIK this has no closed form solution, and I wonder if there are reasonable estimates of its maximal root in terms of $p,q,r,s$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.