Finding the $3 \times 3$ binary matrix with the least spectral radius greater than $1$ Let $A$ be a $3 \times 3$ matrix whose elements are only $0$ and $1$. Let $|\lambda_A^{\max}|$ be the spectral radius, i.e., the maximum absolute value of eigenvalues of $A$.
How can I choose the matrix $A$ such that $\log |\lambda_A^{\max}|$ has the minimal positive value?
Can someone give me a hint? Thank you!
 A: (The other answer here has already addressed the OP's problem. We consider the general case below only for future reference.)
For every $n\ge2$, denote by $\mathcal B_n$ the set of all nonzero $n\times n$ binary matrices. It is an easy consequence of Perron-Frobenius theorem that $\rho(A)\ge1$ if $A\in\mathcal B_n$ is irreducible. Let
\begin{align*}
r_n &= \min_{A\in\mathcal B_n,\ \rho(A)>1}\log\rho(A),\tag{1}\\
A_n &= \arg\min_{A\in\mathcal B_n,\ \rho(A)>1}\log\rho(A).\tag{2}
\end{align*}
Note that if $A$ is an irreducible nonnegative matrix and we increase the values of some of its entries, the spectral radius of the resulting matrix must strictly increase (see Theorem about positive matrices for proofs). Furthermore, if $A$ is also binary, it must contain a full-cycle graph, i.e. $A\ge P$ for some irreducible permutation matrix $P$. It follows that if $A_n$ is the minimiser in $(2)$, there are only two possibilities:

*

*$A_n$ is reducible and hence $r_n=r_m$ for some $m<n$.

*$A_n$ is obtained by flipping a zero entry of an irreducible permutation matrix to $1$.

Consequently, if we define

$\rho_n:=$ the minimum possible spectral radius of an $n\times n$ matrix $A$ obtained by flipping a zero entry of an irreducible permutation matrix to $1$,

then $r_n=\min(\rho_2,\rho_3,\ldots,\rho_n)$. We now prove that $\{\rho_n\}$ is actually a decreasing sequence and hence $r_n=\rho_n$.
Proof.
Let $A$ be a matrix obtained by flipping a zero entry of an irreducible permutation matrix $P$ to $1$, i.e. $A=P+E_{i_0j_0}$ for some $E_{i_0j_0}$ such that $j_0\ne\sigma(i_0)$, where $P$ corresponds to the full cycle $\sigma$. Recall that $\rho(A)>\rho(P)=1$.
Let $v$ be a Perron vector for $A$. By relabelling the rows and columns of $A$, we may assume without loss of generality that $0<v_1\le v_2\le\cdots\le v_n$. Since $\rho(A)v=Av=Pv+E_{i_0j_0}v$, we have
\begin{align*}
\rho(A)v_i &= v_{\sigma(i)}&\text{ if } i\ne i_0,\tag{3}\\
\rho(A)v_{i_0} &= v_{\sigma(i_0)}+v_{j_0}.\tag{4}
\end{align*}
It follows that $i_0=n$, otherwise by putting $i=n$ in $(3)$, we get $\rho(A)v_n = v_{\sigma(n)}\le v_n$, which is a contradiction because $\rho(A)>1$. Thus we may rewrite $(3)$ and $(4)$ as
\begin{align*}
\rho(A)v_i &= v_{\sigma(i)}&\text{ if } i<n,\tag{5}\\
\rho(A)v_n &= v_{\sigma(n)}+v_{j_0}.\tag{6}
\end{align*}
Thus it follows from $(5)$ that $\sigma(n-1)=n$, otherwise we would have
$\rho(A)v_{n-1}=v_k$ for some $k<n$, which is again a contradiction to $\rho(A)>1$. So, inductively, we have $\sigma(i)=i+1$ for $i=n-1,\,n-2,\ldots$ down to $1$ and in turn, $\sigma(n)$ must be equal to $1$. In other words,
\begin{align*}
\rho(A)v_i &= v_{i+1}&\text{ if } i<n,\tag{7}\\
\rho(A)v_n &= v_1+v_{j_0}.\tag{8}
\end{align*}
Hence by $(7)$, $v_i=\rho(A)^{i-1}v_1$ for every $i<n$, and by $(8)$, $\rho(A)^n = 1 + \rho(A)^{j_0}$ where $j_0<n$. It follows that $\rho(A)$ is a root to the polynomial equation
$$
f_{j_0}(x) := x^n - x^{j_0-1} - 1 = 0\tag{9}
$$
on the domain $x>1$. Since $f_{j_0}(x)$ is strictly increasing in $x$ but strictly decreasing in $j_0$, the root of $f_{j_0}$ is unique and it is minimised when $j_0$ is minimised, i.e. when $j_0=2$.
So, we conclude that $\rho_n$ is the positive root of $g_n(x):=x^n-x-1=0$ on $x>1$. As $g_n(x)$ is strictly increasing in both $x$ and $n$, we see that $\{\rho_n\}$ is a strictly decreasing sequence. Hence $r_n=\rho_n$.
In short, for every $n\ge2$, the global minimiser $A_n$ of $r_n$, up to permutation similarity, is uniquely given by the companion matrix of $x^n-x-1$, i.e.
$$
A_n=\pmatrix{0&1\\ \vdots&&\ddots\\ \vdots&&&\ddots\\ 0&&&&1\\ 1&\color{red}{1}&0&\cdots&0},
$$
and $\rho(A_n)$ is the unique positive root of $x^n-x-1=0$ on $x>1$.
A: I ran the following script on Matlab.  Some strange workarounds were necessary because my version is out of date.
Lmin = 3;
imin = 0;
Amin = zeros(3);

for i = 0:511
    b = dec2bin(i,9) == '1';
    A = reshape(b, [3,3]) + zeros(3);
    L = eigs(A,1);
    if L > 1.01 && L < Lmin
        Amin = A;
        Lmin = L;
        imin = i;
    end
end

The minimum is attained with
$$
A = \pmatrix{0&0&1\\1&0&1\\0&1&0}, \qquad \lambda_{max} \approx 1.3247
$$
I'm exploiting the fact that non-negative matrices always have a non-negative eigenvalue which coincides with the spectral radius.  We get the same even if we have L = max(abs(eig(A))).
