Dear MathTalk,

The second of my new set of puzzles:

Let M be a square matrix of size n. 
Let M be row stochastic.
Let M be irreducible (and, if it helps) aperiodic.
Let each row in M have strictly fewer than n/2 non-zero entries.

Can we find an easily invertable matrix T such that matrix R, which is
defined as TMT^{-1}, is row stochastic, irreducible, and at least one
of the rows in R has strictly more than n/2 non-zero entries.

Many thanks again,

Dooogle

---

Clarification of Question by dooogle-ga on 14 Sep 2005 06:14 PDT

Dear MathTalk,
In answer to your comment, I don't mind negative entries being
introduced, but then I'd like to introduce absolute values into the
definition of R.

So, to clarify: 
Let M be such for all i,j M_{ij}>=0  and that for all i \sum_j M_{ij} = 1.

Let R be such that for all i \sum_j |R_{ij}| = 1. That is to say,
given the possibility of negative entries, I want the absolute values
fo the row entries to sum to 1.

[Actually, I don't mind if  \sum_j |R_{ij}| <= 1.]

Thanks,

Dooogle

---

Clarification of Question by dooogle-ga on 14 Sep 2005 06:24 PDT

If such a matrix T can be shown theoretically to exist, two
interesting metaquestions: how would one go about finding such a
matrix T in practice; and could we easily find such a matrix T which,
while making one of the rows of R dense, does not unduly render the
entire matrix R dense (given that M was defined to be sparse)?

Thanks,

Dooogle

---

Clarification of Question by dooogle-ga on 15 Sep 2005 03:17 PDT

Apologies if I wasn't clear in my reponse to your comments.

Let me try again.


Let M be a square matrix of size n. 
Let M be such that for all i,j M_{ij}>=0 and for all i \sum_j M_{ij}=1
Let M be irreducible (and, if it helps) aperiodic.
Let each row in M have strictly fewer than n/2 non-zero entries.

Can we find an easily invertable matrix T such that matrix R, which is
defined as TMT^{-1}, is irreducible, is such that for all i \sum_j
|R_{ij}| <=1 and at least one of the rows in R has strictly more than
n/2 non-zero entries.

Thanks,

Dooogle

The definition of stochastic matrix might be worth pinning down in this context:

[Stochastic Matrix -- MathWorld]
http://mathworld.wolfram.com/StochasticMatrix.html

Often what we mean by a (row) stochastic matrix is the probability
transition matrix of a finite Markov chain.  Rows correspond to states
in the "diagram" and the entries of the row represent probabilities of
transition to another state corfresponding to the column.  Naturally
the probabilities in each row add up to 1, and of course all the
entries are nonnegative.

One may also mean that a (row) stochastic matrix is one that has
entries (perhaps from an arbitrary field) such that every row sums to
1, without requiring the probability interpretation, ie. that entries
be nonnegative (as would of course not be a consideration if the field
were not an ordered field).

It is relatively easy to "fill in" zero entries of a stochastic matrix
by a similarity transformation that produces another stochastic
matrix, if what one has in mind is the second definition.

If one is thinking of the stricter first definition, then for both M
and TMT?¹ to be stochastic, T must be (up to some scalar multiple)
"row stochastic" in the second sense, ie. that Tu = u where u =
(1,1,...,1)'.  It appears quite difficult to find examples of
similarity transformations under these constraints that do not
introduce negative entries.


regards, mathtalk-ga

Note that if a row sum of R is equal to 1, then the sum of absolute
values of those row entries must be greater than or equal to 1, with
equality only if all the entries are nonnegative.  So allowing
negative entries in R is not consistent with requiring both that the
"absolute value" row sums are less than or equal to 1 and the row sums
are equal to 1.

Possibly you are interested in more general similarity
transformations, which do not preserve row "stochasticness" in even
the second (weaker) sense.


regards, mathtalk-ga

Here is a fairly minimal example of what you've asked for.  To have a
majority of entries in every row be zero, without getting an identity
or permutation matrix, we need at least two nonzero entries in some
row out of (then) a total of five.

        / 1/2  1/2   0    0    0  \
        |  0   1/2  1/2   0    0  |
Let M = |  0    0   1/2  1/2   0  |
        |  0    0    0   1/2  1/2 |
        \  0    0    0    0    1  /


        / 1/5  1/5  1/5  1/5  1/5 \
        |  0    1    0    0    0  |
and T = |  0    0    1    0    0  |
        |  0    0    0

/ 1/5  1/5  1/5  1/5  1/5 \
        |  0    1    0    0    0  |
and T = |  0    0    1    0    0  |
        |  0    0    0    1    0  |
        \  0    0    0    0    1  /

Then R = T M T?¹ will be row stochastic and the top row's entries will
all be nonzero:

        / 1/2  0.1  0.1  0.1  1/5 \
        |  0   1/2  1/2   0    0  |
    R = |  0    0   1/2  1/2   0  |
        |  0    0    0   1/2  1/2 |
        \  0    0    0    0    1  /

Probably something of this kind can be done generally, given that the
original matrix M is irreducible and aperiodic.


regards, mathtalk-ga

Hi, dooogle-ga:

I didn't think there was confusion, but if so, is the above an example
of what you are seeking, ie. does R = T M T?¹ satisfy all the criteria
or not in this case?

regards, mathtalk-ga

Dear MathTalk,

Yes, this is indeed an example of what I'm looking for - all criteria
are cheerfully satisfied.

A general approach along these lines is exactly what is required.

Thank you,
Dooogle

(Incidently, if R has negative entries, I'm actually looking for the
number of postive entries to exceed n/2 - not just the number of
non-zeros.)

Some thoughts on the example given:

Am I correct in thinking that T^{-1} is given by:
5 -1 -1 -1 -1
0  1  0  0  0
0  0  1  0  0
0  0  0  1  0
0  0  0  0  1

Also, the M matrix given in the example is not irreducible.
If the last row of M were to read:
1/2 0 0 0 1/2
then the matrix would be irreducible and aperiodic.
But, then, unless I'm mistaken, we wouldn't end up with the entirely
positive first row in R.

Dooogle.