Spectrum of a matrix that has only one $1$ in each row

273 Views Asked by At

As in the title, I'm searching for the spectrum of a matrix which has only one $1$ in each row (and zeros as other entries) and also that is not necessary a permutation matrix. For example,

$$A =\begin{bmatrix} 1 & 0 &0 \\ 1 &0 &0\\ 0 & 1 &0 \end{bmatrix}$$

Is it true that the specrum of such a thing only contains eigenvalues $\lambda$ of $|\lambda|=1$ or $\lambda = 0$?

1

There are 1 best solutions below

4
On BEST ANSWER

Let $A\in\mathcal{M}_n(\mathbb{R})$ such that for all $i\in[\![1,n]\!]$ there exists $f(i)\in[\![1,n]\!]$ such that $a_{i,f(i)}=1$ and $a_{i,j}=0$ for all $j\neq f(i)$, that is to say $a_{i,j}=\delta_{f(i),j}$. According to Gerschgorin circle theorem, if $\lambda$ is an eigenvalue of $A$, then $$ \lambda\in\bigcup_{i\in[\![1,n]\!]}D\left(a_{i,i},\sum_{j\neq i}|a_{j,i}|\right) $$ where $D(a,r)=\{z\in\mathbb{C}\ |\ |z-a|\leqslant r\}$. But, if $a_{i,i}=1$, then $f(i)=i$ and thus $\sum_{j\neq i}|a_{j,i}|=0$ which means that $D\left(a_{i,i},\sum_{j\neq i}|a_{j,i}|\right)=\{1\}$. If $a_{i,i}=0$ then $\sum_{j\neq i}|a_{j,i}|=1$ and $D\left(a_{i,i},\sum_{j\neq i}|a_{j,i}|\right)=D(0,1)$. This means that all the eigenvalues of $A$ are in $D(0,1)$ and thus all the roots of $\chi_A$ are in $D(0,1)$. Since $A\in\mathcal{M}_n(\mathbb{Z})$, $\chi_A\in\mathbb{Z}[X]$ and according to Kronecker's theorem, all the roots of $\chi_A$ are either $0$ or a root of unity. This means that all the eigenvalues of $A$ are such that $\lambda=0$ or $|\lambda|=1$.

Kronecker's theorem : Let $P\in\mathbb{Z}[X]$ a monic polynomial (that is to say its leading coefficient is $1$) such that all the roots of $P$ are in $D(0,1)$, then the roots of $P$ are $0$ or roots of unity.

Proof : Let $\Omega_n:=\{P\in\mathbb{Z}[X]\ |\ \deg P=n,P \text{ is a monic polynomial and the roots of }P\text{ are in }D(0,1)\}$. $\Omega_n$ is finite because if $P=\sum_{k=0}^na_kX^k\in\Omega_n$ and $z_1,\ldots,z_n$ are the roots of $P$ then $$ |a_{n-k}|=\left|\sum_{1\leqslant i_1<\ldots<i_k\leqslant n}z_1\ldots z_k\right|\leqslant\sum_{1\leqslant i_1<\ldots<i_k\leqslant n}\underbrace{|z_1|}_{\leqslant 1}\ldots\underbrace{|z_k|}_{\leqslant 1}\leqslant\binom{n}{k} $$ Since $a_{n-k}\in\mathbb{Z}$, $a_{n-k}$ can only take a finite number of values and thus $\Omega_n$ is finite. Since any $P\in\Omega_n$ has at most $n$ roots, the set of the roots of elements of $\Omega_n$ is finite. Let $P\in\Omega_n$ and $z_1,\ldots,z_n$ its roots so that $P=\prod_{i=1}^n(X-z_i)$. Let $C_P$ the companion matrix of $P$ and let $P_k=\prod_{i=1}^n(X-z_i^k)$ for $k\in\mathbb{N}$. Since $P\in\mathbb{Z}[X]$, $C_P\in\mathcal{M}_n(\mathbb{Z})$ and, if we triangularize $C_P$ in $\mathbb{C}$, there exists $Q\in\text{GL}_n(\mathbb{C})$ such that $$ C_P=Q\begin{pmatrix}z_1 &\star &\ldots &\ldots &\star \\ 0 &\ddots &\ddots & &\vdots \\ \vdots & &\ddots &\ddots &\star \\ 0 &\ldots &\ldots &0 &z_n \end{pmatrix}Q^{-1} $$ Thus for all $k\in\mathbb{N}$, $$ C_P^k=Q\begin{pmatrix}z_1^k &\star &\ldots &\ldots &\star \\ 0 &\ddots &\ddots & &\vdots \\ \vdots & &\ddots &\ddots &\star \\ 0 &\ldots &\ldots &0 &z_n^k \end{pmatrix}Q^{-1} $$ so that $\chi_{C_P^k}=P_k$. But $C_P\in\mathcal{M}_n(\mathbb{Z})$ so $C_P^k\in\mathcal{M}_n(\mathbb{Z})$ and thus $P_k\in\mathbb{Z}[X]$. You finally have that if $z\in\mathbb{C}$ is a root of an element of $\Omega_n$, then $z^k$ is a root of an element of $\Omega_n$ for all $k\in\mathbb{N}$. However the set of the roots of elements of $\Omega_n$ is finite so the sequence $(z^k)_{k\in\mathbb{N}}$ can't be injective. Thus there exists $(k, \ell)\in\mathbb{N}^2$ such that $z^k=z^{\ell}$. Either $z=0$ or $z\neq 0$ and there $z^{\ell-k}=1$ so $z$ is a root of unity.