1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Aug 12, 2020 at 20:58

1 Answer 1

2
$\begingroup$

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$.

edit: addendum
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).

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Leonidas
    Commented Aug 12, 2020 at 22:01
  • $\begingroup$ 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). $\endgroup$ Commented Aug 12, 2020 at 23:03
  • $\begingroup$ 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! $\endgroup$
    – Leonidas
    Commented Aug 13, 2020 at 16:36
  • $\begingroup$ 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. $\endgroup$ Commented Aug 13, 2020 at 17:34
  • $\begingroup$ Thanks a lot for the clarification! I will look at this more carefully a bit later today. $\endgroup$
    – Leonidas
    Commented Aug 13, 2020 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .