Preposition about the Entries of the Product of Markov Matrices.

120 Views Asked by At

Definition: A Markov matrix is an $n \times n$ complex matrix with the sum of the elements in every column equal to 1.

My task is to prove that: If A, B are Markov matrices such that $|a_{ij}|\leq1$ and $|b_{ij}|\leq1$ for all i, j and if $A B = C = (c_{ij})$, then $|c_{ij}|\leq1$ for all i, j.

Note: In this case $|z|$ denotes the standard complex norm $\sqrt{a^2+b^2}$, where $z=a+bi$.

One potentially useful fact that I am aware of is that if $A, B$ are Markov matrices, then so is $AB$.

1

There are 1 best solutions below

0
On BEST ANSWER

$$\newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\conj}[1]{\overline{#1}}$$

It turns out that the preposition is just plain false. The author made a mistake.

Consider the complex number: $\omega = \frac{1-i\sqrt{3}}{2}$.

By the author's definition of $\abs{z}$, $$ \abs{\omega} = \abs{\conj{\omega}}= \sqrt{\Bigl(\frac{1}{2}\Bigr)^2+\Bigl(\frac{\sqrt{3}}{2}\Bigr)^2} = \sqrt{\frac{1}{4}+\frac{3}{4}} = 1 $$

Now, let:

$ M = \begin{bmatrix} \omega&\conj{\omega}\\ \conj{\omega}&\omega \end{bmatrix}\;and\; N = \begin{bmatrix} \conj{\omega}&\omega\\ \omega&\conj{\omega} \end{bmatrix} $

M and N are both Markov matrix by the author's definition, since $\omega + \conj{\omega} = 1$. It is furthermore true $\abs{a_{ij}} \leq 1$ for all entries of both M and N.

But $ M \times N = \begin{bmatrix} \omega&\conj{\omega}\\ \conj{\omega}&\omega \end{bmatrix} \times \begin{bmatrix} \conj{\omega}&\omega\\ \omega&\conj{\omega} \end{bmatrix} = \begin{bmatrix} 2\omega\conj{\omega}&*\\ *&* \end{bmatrix} = \begin{bmatrix} 2 \times 1&*\\ *&* \end{bmatrix} = \begin{bmatrix} 2&*\\ *&* \end{bmatrix} $. Therefore the product does not satisfy the condition that all entries have absolute value less than or equal to one, and thus the preposition is false.