2
$\begingroup$

...or prove that none exists.

Note that such a matrix M couldn't be primitive, so there would be at least one entry equal to zero in every power M^k (Perron-Frobenius theory).

Preferably the matrix would have a diagonal that is not all zero, and at the risk of making the problem imprecise, I'd like to find such a matrix with as few zeros and ones as possible.

Thank you.

$\endgroup$
  • $\begingroup$ Take a permutation matrix corresponding to an n-cycle $\endgroup$ – Benjamin Steinberg Apr 12 '16 at 0:49
  • $\begingroup$ Ben, sorry, question fixed. $\endgroup$ – tarski Apr 12 '16 at 1:34
  • $\begingroup$ The matrix [[0,1,0],[1,0,0],[0,0,0]] meets your description (it has an eigenvalue of -1), but I'm guessing that's not what you intended. Maybe you want to require the eigenvalue to be non-real? $\endgroup$ – Bill Bradley Apr 12 '16 at 2:37
  • $\begingroup$ @Bill, that's not stochastic (but if you change the last row to $[0,0,1]$, it is). $\endgroup$ – Gerry Myerson Apr 12 '16 at 2:55
  • $\begingroup$ @GerryMyerson, but if you make said change it becomes a permutation matrix. $\endgroup$ – tarski Apr 12 '16 at 3:10
6
$\begingroup$

$$\pmatrix{0&1&.5\cr1&0&.5\cr0&0&0\cr}$$ has $-1$ as an eigenvalue.

$\endgroup$
  • $\begingroup$ All the column sums are 1, all the entries are non-negative. What definition are you using? (If you want the rows to sum to 1, just take the transpose). $\endgroup$ – Gerry Myerson Apr 12 '16 at 3:58
1
$\begingroup$

If you want a doubly stochastic matrix, $$\begin{pmatrix} 0&1 & 0&0&0 \\ 1&0 & 0&0&0 \\ 0&0 & 1/3&1/3&1/3 \\ 0&0 & 1/3&1/3&1/3 \\ 0&0 & 1/3&1/3&1/3 \\ \end{pmatrix}$$ has eigenvalue $-1$.

$\endgroup$
1
$\begingroup$

The Karpelevič theorem will make it difficult for the matrix not to at least involve a permutation matrix (notice that the upper-left $2$-by-$2$ block of the matrix given by Gerry is a permutation matrix).

If $C_n$ is the $n$-by-$n$ defined by $C_n = [e_n \mid e_1 \mid \cdots \mid e_{n-1}]$, i.e., $C_n$ is the adjancency matrix of a directed $n$-cycle, where $e_i$ denotes the $i^\text{th}$ canonical basis vector of $\mathbb{C}^n$, then the $n$-by-$n$ (row) stochastic matrix $$ M_n := \begin{bmatrix} 0 & e_1^\top \\ 0 & C_{n-1} \end{bmatrix}$$ has spectrum $\sigma(M) = \{ 0, 1, \omega,\dots,\omega^{n-1}\}$, where $\omega:=\exp(2\pi i/n)$. Thus, $M_n$ has $n-2$ eigenvalues (distinct from unity) on the unit-circle.

For instance, the matrix $$ M_5= \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ \end{bmatrix} $$ has spectrum $\{0,\pm 1, \pm i\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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