The trace conjecture for banded substochastic matrices

Smallest rational counterexample. Set $k=2$ and

$$A=\frac13 \begin{pmatrix} 1&2&0\\ 0&1&2\\ 2&0&1 \end{pmatrix} =\frac13I+\frac23P,\qquad P^3=I.$$

Every entry is nonnegative, every row and column sums to one, and all entries are constant on each diagonal. The only nonzero diagonal above the main diagonal has distance one; the only nonzero diagonal below it has distance two. Thus $A$ satisfies both the general hypotheses and the stronger Toeplitz hypotheses exactly. Since $\operatorname{Tr}P=\operatorname{Tr}P^2=0$,

$$\bigl(\operatorname{Tr}A,\operatorname{Tr}A^2, \operatorname{Tr}A^3,\operatorname{Tr}A^4\bigr) =\left(1,\frac13,1,\frac{11}{9}\right).$$

All required traces through $k+1=3$ are at most one, but the very next trace exceeds one.

In fact, both conjectures fail at every bandwidth $k\ge2$. Put $L=k+1$, let $P_L$ be the cyclic permutation matrix with ones on the first superdiagonal and at entry $(L,1)$, and set

$$a=\frac1L,\qquad b=\left(\frac1L-\frac1{L^L}\right)^{1/L}, \qquad A_L=aI_L+bP_L.$$

The matrix is nonnegative, Toeplitz, and has the prescribed upper bandwidth one and lower bandwidth $k$. For $L=3$, $a+b=1$. For $L\ge4$,

$$(1-1/L)^L\ge(3/4)^4 =\frac{81}{256}>\frac14\ge\frac1L>b^L,$$

so $a+b<1$. Hence every row and column sum is at most one.

Because $\operatorname{Tr}(P_L^j)=L$ when $L\mid j$ and vanishes otherwise, the binomial theorem gives

$$\operatorname{Tr}(A_L^j)=L^{1-j}\le1 \quad(1\le j<L),$$ $$\operatorname{Tr}(A_L^L)=L(a^L+b^L)=1,$$

but

$$\operatorname{Tr}(A_L^{L+1}) =1+\frac1L-L^{1-L}>1.$$

Thus failure occurs already at exponent $k+2$ for every $k\ge2$.

Sharp positive boundary: $k=1$. For any nonnegative tridiagonal row-substochastic matrix $A$, with diagonal $d_i$, superdiagonal $u_i$, and subdiagonal $v_i$, define the symmetric tridiagonal matrix $S$ by

$$S_{ii}=d_i,\qquad S_{i,i+1}=S_{i+1,i}=\sqrt{u_iv_i}.$$

The leading principal characteristic polynomials of both matrices satisfy

$$D_0=1,\quad D_1(t)=t-d_1,\quad D_j(t)=(t-d_j)D_{j-1}(t)-u_{j-1}v_{j-1}D_{j-2}(t).$$

Therefore $A$ has the same real eigenvalues $\lambda_i$ as $S$, and row substochasticity gives $|\lambda_i|\le1$. If $\operatorname{Tr}A^2\le1$, then for every $j\ge2$,

$$\operatorname{Tr}A^j =\sum_i\lambda_i^j \le\sum_i|\lambda_i|^j \le\sum_i\lambda_i^2 =\operatorname{Tr}A^2\le1.$$

Together with the separately assumed first-trace bound, this proves the exact classification:

$$\boxed{k=1:\ \text{true};\qquad k\ge2:\ \text{false}.}$$

This simultaneously settles the general and Toeplitz finite-matrix assertions. The separate infinite return-probability assertion is not addressed.

Source: J. C. Mehta, Conjectures 4.38 and 4.39, pp. 101–102.