Eigenvalues and Conditioning of a Cyclic Permutation Matrix
Consider the $n \times n$ matrix $A$ defined by $A_{i, i+1} = 1$ for $i = 1, 2, \ldots, n-1$, and $A_{n, 1} = 1$, with every other entry equal to $0$. In words, $A$ is the cyclic shift: it has a single
- What are the eigenvalues of $A$?
- What is the condition number of $A$ (use the
- As $n \to \infty$, what happens to the eigenvalues and to the condition number?
Hints
- Notice what $A$ does to a coordinate vector. What happens if you apply $A$ repeatedly $n$ times?
- If $A^n = I$, every eigenvalue must be an $n$-th root of unity. For the condition number, ask whether $A$ is orthogonal -- check $A^{\top}A$.
- An orthogonal matrix has all singular values equal to $, so its$-norm condition number is exactly$ regardless of $n$. Do not confuse eigenvalues (on the unit circle) with singular values (all$).
Worked Solution
How to Think About It: Do not reach for the characteristic polynomial directly -- recognize the structure first. $A$ is a permutation matrix that sends basis vector $e_i$ to $e_{i-1}$ (cyclically), i.e. it implements the cyclic shift. Applying it $n$ times returns every vector to where it started, so $A^n = I$. That single fact pins down the eigenvalues: they must be $n$-th roots of unity. A trader's instinct: a pure permutation just relabels coordinates, it never stretches or shrinks any vector, so it should be perfectly conditioned.
Quick Estimate: Since $A^n = I$, every eigenvalue $\lambda$ satisfies $\lambda^n = 1$. There are exactly $n$ distinct such values, and $A$ has $n$ distinct eigenvalues, so the eigenvalues are precisely all the $n$-th roots of unity. They all sit on the unit circle, so $|\lambda| = 1$ for each.
Formal Solution: The eigenvalues are $\lambda_k = e^{2\pi i k / n}, \quad k = 0, 1, \ldots, n-1.$ This is the standard spectrum of the cyclic permutation (circulant generator). For the condition number we need singular values, not eigenvalues. $A$ is a real permutation matrix, hence orthogonal: $A^{\top} A = I$. All singular values of an orthogonal matrix equal
$. Therefore $\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}} = \frac{1}{1} = 1.$Behavior as $n \to \infty$: The eigenvalues remain on the unit circle and simply fill it in more densely (the $n$-th roots of unity become an ever finer mesh around $|z| = 1$); their magnitudes stay fixed at
$. The condition number stays exactly$ for every $n$ -- it does not grow. The matrix is perfectly conditioned no matter how large it gets.$-norm condition number isAnswer: Eigenvalues are the $n$-th roots of unity $e^{2\pi i k/n}$, all on the unit circle. The
$ for all $n$ (the matrix is orthogonal), and it stays$ as $n \to \infty$ while the eigenvalues densely populate the unit circle.Intuition
The trap this problem sets is conflating eigenvalues with singular values. The eigenvalues of $A$ are complex numbers spread around the unit circle, which might make you think the matrix is somehow exotic or ill-behaved. But conditioning is about singular values, and for a permutation matrix every singular value is
$ -- it just relabels coordinates without distorting lengths. A matrix can have wild-looking complex eigenvalues and still be perfectly conditioned.This distinction matters constantly in quant work. When you solve a linear system or invert a covariance matrix, numerical stability is governed by the condition number (the singular-value ratio), not by where the eigenvalues sit. Normal matrices line the two up, but the moment a matrix is non-symmetric the two can diverge dramatically, and an interviewer at an HFT shop wants to see that you know which one controls floating-point error.