8
$\begingroup$

I am trying to determine whether the following, $ n $ by $ n $ matrix:

$$ A = \begin{pmatrix} \Delta_{11} - 1 & \Delta_{12} & ... & \Delta_{1n} \\ \Delta_{21} & \Delta_{22} - 1 & ... & \Delta_{2n} \\ ... \\ \Delta_{n1} & \Delta_{n2} & ... & \Delta_{nn} - 1 \end{pmatrix} $$

Subject to $ \Delta_{ij} \in [0,1] $ and:

$$ 0 < \sum_{j=1}^{n}\Delta_{ij} < 1, \text{ } \forall i $$

Is invertible in general or not. I started out by noticing that this is equivalent to saying that the matrix $ \Delta = A + I $ does not have an eigenvalue equal to one. I was hoping that, since $ \Delta $ is "almost a Markov matrix" (i.e. the rows do not add up to one, but all the other properties are there), and we know that Markov matrices have an eigenvalue equal to one, then maybe I can squeeze out a proof that such an "almost Markov matrix" does not have an eigenvalue equal to one - but so far I've been unsuccessful.

$\endgroup$
2

2 Answers 2

9
$\begingroup$

We prove by indirection that the matrix will be diagonally dominant (Note 1), therefore invertible (Note 2).

Assume otherwise so that for some row $i$,

$|\Delta_{ii}-1|\le\sum\limits _{j\not=i}|\Delta_{ij}|.$

From the hypotheses, $\Delta_{ii}-1$ is negative and $\Delta_{ij}$ is positive, so the inequality rearranges to

$1-\Delta_{ii}\le\sum\limits _{j\not=i}\Delta_{ij}$

$\sum\limits _{\text{all }j}\Delta_{ij}\ge1.$

This directly contradicts the hypothesis, so denying diagonal dominance must be false. With the matrix thus proven diagonally dominant it must then be invertible.

Notes

  1. (Row) Diagonal dominance: the absolute value of each diagonal element exceeds the sum of absolute values of all other elements in its row.

  2. Multiply each row by the multiplicative inverse of its diagonal element, which will not alter invertibility or diagonal dominance. The result can be exptessed as $I+M$ where the elements of $M$ are so small its $L_1$ norm is less than $1$. So the eigenvalues of $I+M$ are each $1$ plus a number with a smaller absolute value and can never reach zero. Thus $I+M$ is invertible. The row operation could not magically create this invertolibility, therefore the original matrix must be invertible too.

$\endgroup$
0
7
$\begingroup$

You're on the right path by noting that $A$ is not invertible if and only if $\Delta$ has an eigenvalue equal to $1$. This means that there is a non-zero vector $v$ such that $v=\Delta v$. But each entry of $\Delta $ has absolute value strictly less than $1$ (so as not to contradict the summation hypothesis), so $$ \|v\|_\infty = \|\Delta v\|_\infty \leq \|\Delta \|_\infty \|v\|_\infty < 1 \cdot \|v\|_\infty = \|v\|_\infty, $$ a contradiction.

$\endgroup$

You must log in to answer this question.

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