Proving that $\det(I-T_i) >0$ where $T$ is a primitive stochastic matrix and $T_i$ is a principal submatrix

Let $$T$$ be an $$n \times n$$ row-stochastic matrix which is primitive (i.e. there is a positive integer $$k$$ such that all entries of $$T^k$$ are strictly positive). Let $$T_i$$ denote the matrix obtained by eliminating the $$i$$th row and $$i$$th column from $$T$$. How do I prove that $$\det(I - T_i) > 0 \quad \text{for all } i \; ?$$

($$I$$ denotes the $$(n-1) \times (n-1)$$ identity matrix.)

Here are some facts that may be relevant:

1 is an eigenvalue of $$T$$.
If $$\lambda$$ is an eigenvalue of $$T$$ then $$|\lambda| \leq 1$$.
If $$\lambda_1,\lambda_2,\ldots,\lambda_n$$ are the eigenvalues of $$T_i$$, then $$1-\lambda_1,1-\lambda_2,\ldots,1-\lambda_n$$ are the eigenvalues of $$I-T_i$$.
A sufficient condition for $$\det(I-T_i)>0$$ is to have all eigenvalues of $$I-T_i$$ be strictly positive. So in light of the previous fact, it sufficies to show that the eigenvalues of $$T_i$$ are all strictly less than 1. But I don't know how to rigorously establish this.

• If we remove state $i$ and connect every $j$ that goes to $i$ with probability $p_{j,i}$ with every $k$ that leaves $i$ with probability $p_{i,k}$ by a probability $\hat{p}_{j,k} = p_{j,k} + p_{j,i}p_{i,k}$ we have another primitive matrix (of the chain minus $i$) that is related to $T_i$. How is it related to $T_i$? Commented Aug 12, 2020 at 20:58

for your problem, which is an offshoot of this:
Question about a proof of the Perron Frobenius Theorem

it suffices to consider the case where $$T$$ is strictly positive (componentwise) and let $$P:=T$$. If this is unsatisfactory consider using $$P:=\frac{1}{n}\big(T+T^2+.... T^n\big)$$ which must be strictly positive componentwise, and observe that $$P$$ and $$T$$ have the same algebraic multiplicity of $$\lambda_1 =1$$.

Now $$P\mathbf 1_n = \mathbf 1_n$$ and
$$P_i\mathbf 1_{n-1} \lt \mathbf 1_{n-1}$$ (component-wise)
$$\longrightarrow \text{spectral radius}(P_i) =\sigma(P_i)\lt 1$$ by Gerschgorin Discs.

In general $$\det(Ix - B)$$ is a monic real polynomial in x and thus its image is $$\gt 0$$ for large enough $$x$$. Let $$B:= P_i$$. We know $$\det(I - P_i)\neq 0$$ since $$\sigma(P_i)\lt 1$$ and if $$\det(I - P_i)\lt 0$$ then by intermediate value theorem there is some $$x'\gt 1$$ such that $$\det(Ix' - P_i)= 0$$ but this contradicts $$\sigma(P_i)\lt 1$$.

We conclude $$\det(I - P_i)\gt 0$$.

to explain in a very granular way as to why the algebraic multiplicity of $$\lambda_1=1$$ is the same for $$P=\frac{1}{n}\big(T+T^2+.... T^n\big)$$ and $$T$$

0.) for upper triangular matrix $$R$$, $$\det\big(xI - R\big)=\prod_{j=1}^n (x-r_{j,j})$$ so the algebraic multiplicity of some eigenvalue comes down to counting how many times it shows up on the diagonal

1.) over $$\mathbb C$$ every matrix is similar to an upper triangular matrix (e.g. using Schur Triangularization for a light weight approach), and similarity transforms do not affect the char poly/eigenvalues

2.) use a similarity transform to triangularize $$T$$
$$R= S^{-1}TS \longrightarrow U= S^{-1}PS = \frac{1}{n}\big(R+R^2+.... + R^n\big)$$
where $$U$$ is necessarily upper triangular

3.) $$\text{eigenvalue j of R is 1} \longrightarrow \text{eigenvalue j of U is 1}$$
$$u_{j,j}= \frac{1}{n}\big(r_{j,j}+r_{j,j}^2+....+ r_{j,j}^n\big) = \frac{1}{n}\big(1+1+.... + 1\big) =1$$

4.) $$\text{eigenvalue j of R is not 1} \longrightarrow \text{eigenvalue j of U is not 1}$$

to make this extra clear, split into 2 cases, and in each case apply triangle inequality
i.) $$\vert r_{j,j}\vert \lt 1$$
$$\vert u_{j,j}\vert$$
$$= \frac{1}{n}\Big\vert r_{j,j}+r_{j,j}^2+....+ r_{j,j}^n\Big\vert$$
$$\leq \frac{1}{n}\Big(\big\vert r_{j,j}\vert +\vert r_{j,j}\vert ^2+....+ \vert r_{j,j}\vert^n\Big)$$
$$\leq \frac{1}{n}\Big(\big\vert r_{j,j}\vert +\vert r_{j,j}\vert +....+ \vert r_{j,j}\vert\Big)$$
$$\lt 1$$

ii.) $$\vert r_{j,j}\vert = 1$$ but $$r_{j,j} \neq 1$$
$$\vert u_{j,j}\vert$$
$$= \frac{1}{n}\Big\vert r_{j,j}+r_{j,j}^2+....+ r_{j,j}^n\Big\vert$$
$$\lt \frac{1}{n}\Big(\big\vert r_{j,j}\vert +\vert r_{j,j}\vert ^2+....+ \vert r_{j,j}\vert^n\Big)$$
$$= \frac{1}{n}\Big(1+1+.... +1\Big)$$
$$= 1$$

($$\vert r_{j,j}\vert \gt 1$$ is of course impossible)

so if you count exactly $$m$$ ones on the diagonal of $$R$$ (eigenvalue of T), then there are exactly $$m$$ ones on the diagonal of $$U$$ (eigenvalue of P).

• Thanks for your answer! Could you just explain why $P$ and $T$ have the same algebraic multiplicity of $\lambda_1 = 1$? Also, does $\mathbf{I}_n$ denote a matrix whose entries are all 1? Commented Aug 12, 2020 at 22:01
• I used $\mathbf 1_n$ to denote the n dimensional 1's vector -- in the above post the coordinate vectors are in bold whereas the (square) matrices are not in bold. As for your question re $\lambda_1$ alg multiplicity: use a similarity transform so that $S^{-1}TS =R$ is upper triangular (over $\mathbb C$). The diagonal entries of $R$ that were 1 show up as 1 in $S^{-1}PS$ and all other diagonals of $R$, which have modulus $\leq 1$, result in a value on the diagonal of $S^{-1}PS$ with modulus $\lt 1$ (justification: triangle inequality or explicit computation of finite geometric series). Commented Aug 12, 2020 at 23:03
• Hmm I'm still not quite following the similarity transform part. Are we using the similarity transform to compute the powers of $T$? Perhaps you could edit your answer to flesh out these details a bit more? Thanks in advance and sorry for my weak linear algebra skills! Commented Aug 13, 2020 at 16:36
• I added a rather long addendum to flush out these points in detail. If it still doesn't click you may need to revisit some basics of manipulating upper triangular matrices. Commented Aug 13, 2020 at 17:34
• Thanks a lot for the clarification! I will look at this more carefully a bit later today. Commented Aug 13, 2020 at 17:36