Questions tagged [stochastic-matrices]

A right stochastic matrix is a nonnegative square matrix with each row summing to 1. A left stochastic matrix is a nonnegative square matrix with each column summing to 1. A doubly stochastic matrix is both right stochastic and left stochastic.

Filter by
Sorted by
Tagged with
0
votes
0answers
31 views

How does Pagerank iteratively calculate an eigenvector?

I understand that Pagerank works by finding the eigenvector $\lambda$ to the eigenvalue $\epsilon=1$ of a Markov matrix $A \in \mathbb{R}^{n \times n}$. And, as far as I know, the iterative algorithm ...
0
votes
0answers
18 views

Relationship between the minimal singular value and the matrix size of a stochastic matrix

I have done some numerical experiments. Given a stochastic matrix $A$, the smallest singular value decreases sharply as the matrix size increases. I just want to know whether there are some analyses ...
1
vote
1answer
36 views

What is the steady state of a stochastic matrix if it has two linearly independent eigenvectors corresponding to the eigenvalue $1$?

A stochastic matrix $A$ is a matrix with the following two properties: All entries of $A$ are $\geq 0.$ All columns of $A$ add up to $1$. It is known that for a stochastic matrix, $\lambda = 1$ is ...
1
vote
0answers
32 views

Using the Limit Theorem on a Stochastic Matrix

I have the following Stochastic Matrix $\begin{pmatrix} 0.9 & 0.02 & 0.08 \\ 1-r & r & 0 \\ 0.5 & 0.1 & 0.4 \end{pmatrix}$ I am attempting to work out $P_{i,j} = P(X_n=j | X_0 ...
0
votes
0answers
26 views

$\dfrac{1}{T}\underset{t = 0}{\overset{T - 1}{\sum}}xP^t$ converges

I'm trying to proof that $\dfrac{1}{T}\underset{t = 0}{\overset{T - 1}{\sum}}xP^t$, where x is stochastic vector, P is stochastic matrix, converges. I understand that if there are no eigenvalues of $\...
5
votes
2answers
76 views

Identity relating coefficients of degrees $0$ and $1$ from characteristic polynomials

Let $A$ be a square matrix each of whose columns has sum $1$. Let $B$ be the matrix obtained by replacing the lowest row in $A-I$ with a row of ones. Can anybody show (or find a counterexample) that $...
5
votes
1answer
190 views

Power iteration error for eigenvectors

I'm trying to use the ideas of power iteration to approximate stationary distributions of Markov chains. Let's say I have a left irreducible stochastic matrix $A$ (i.e., non-negative and each column ...
3
votes
1answer
57 views

Spectrum of a matrix that has only one $1$ in each row

As in the title, I'm searching for the spectrum of a matrix which has only one $1$ in each row (and zeros as other entries) and also that is not necessary a permutation matrix. For example, $$A =\...
0
votes
0answers
15 views

Convexity of the product of two convex sets of non-square stochastic matrices

Suppose $X\subseteq\mathbb{R}^{l\times m}$ and $Y\subseteq\mathbb{R}^{m\times n}$ are sets of matrices with real entries. Moreover, $X$ is the set of all $l\times m$ stochastic matrices (each column ...
1
vote
0answers
20 views

Inverse of a stochastic matrix: when is there a strictly negative element?

Let the square matrix $A$ be invertible and left-stochastic (each column adds up to one). Under which conditions is at least one element of the inverse matrix $A^{-1}$ strictly negative? For ...
0
votes
0answers
25 views

Eigenvalues of random stochastic matrix

Let $G=(V,E)$ be some random graph with $|V|=n$, $|E|=m$ and let $\mu\in (0,1)$. Define the random stochastic matrix $P$ of size $n\times n$ for $i,j\in V$ via $P_{ij} = \begin{cases}1- \mathrm{deg}(...
1
vote
0answers
27 views

Spectral radius of the product of a block-diagonal matrix and a row stochastic matrix

Let $W\in\mathbb{R}^{N\times N}$ be a right (row) stochastic matrix with non-negative $ij$ entries $w_{ij}\geq0$, where $\sum_{j=1}^N w_{ij} = 1$, and let $A\in\mathbb{R}^{nN\times nN}$ be a block-...
2
votes
2answers
350 views

How can a Markov chain have more than one but a finite amount of stationary distributions?

Here's my understanding of it: Assume we have an $n\times n$ stochastic matrix $P$ that represents our Markov chain such that $x$ and $y$ are stationary distributions for $P$. Then $P(x) = x$ $P(y) ...
1
vote
1answer
57 views

Formula for powers of $2\times 2$ matrices

Is there a formula for expanding powers of $2\times 2$ matrices? I know that can be done by diagonalizing and then using the spectral decomposition of the matrix, but is there a general formula for $A^...
0
votes
0answers
34 views

The norm of sum of powers of Markov matrix multiply powers of its transpose

I want to show the $L_1$ norm of a matrix $S$ is bounded by something, which is defined as follows. I have tested on some matrices, but I cannot prove it. Let $A$ be a Markov matrix, i.e., $A_{i,j}...
1
vote
0answers
22 views

How to find $P^n_{2,6}$ given this $6 \times 6$ matrix

I have a $ 6 \times 6$ stochastic transition matrix: $$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 &...
1
vote
0answers
72 views

Upper bound on the magnitude of eigenvalue of a stochastic matrix

What is the upper bound for the magnitude of the second largest eigenvalue of the following square matrix $X$ of size $d\times d$? The entries are given as: $X[0,0] = \alpha \in (0,1/d]$, $X[0, d-...
0
votes
1answer
60 views

Eigenvector of stochastic matrix

$P$ is stochastic matrix, $v$ is stochastic vector, $\frac{1}{n}(v + vP + vP^{2} + \cdots + vP^{n}) \to u$. Prove that $uP = u$. I understood that I need to show that u is eigenvector with eigenvalue ...
1
vote
1answer
26 views

Steady state probabilities of divergent Markov matrices

I have a problem for which the Markov matrix turns out to be the following: $$P = \begin{pmatrix} 0 & 0.5 & 0 & 0.5\\ 0.5 & 0 & 0.5 & 0 ...
3
votes
2answers
45 views

Eigenvalues of a special stochastic matrix

I'm trying to find an explicit formula of all the eigenvalues for the following $n$ by $n$ stochastic matrix (sum of each row/column is one): \begin{bmatrix}0&\frac{1}{n-1}&\frac{1}{n-1}&...
0
votes
1answer
23 views

Special non-negative matrix decomposition

Assume we have the following decomposition: $M=AWA^T$ Where: $M$ is non-negative symmetric (i.e. $M_{i,j}\ge{0}$ and $M_{i,j}=M_{j,i}$) $A$ is right stochastic (entries are non-negative and rows ...
2
votes
1answer
29 views

Two Primitive Stochastic Matrices with Eventually Equal Sequence of Powers

Let $A$ and $B$ be two $n\times n$ primitive row-stochastic matrices. That is, all of their entries are non-negative, all the rows sum up to $1$, and there is an integer $p\geq 1$ such that all the ...
1
vote
1answer
41 views

Prove that the set of doubly stochastic $3 \times 3$ matrices is a polyhedron

Let $B_3$ be the set of $3 \times 3$ matrices $M$ with non-negative entries whose rows and columns all add up to $1$. Show that $B_3$ is a polyhedron. Hint: represent a matrix $M$ as a vector $x$ in $\...
4
votes
0answers
92 views

How can one make a periodic Markov chain aperiodic with the smallest change in the main structure of the chain?

Or, how can one "deform" a stochastic, irreducible, periodic matrix into a stochastic, irreducible, aperiodic matrix with the smallest change? If there are several possible procedures, then please ...
1
vote
1answer
89 views

Eigenvalues of stochastic matrices

A stochastic matrix is a real $n\times n$ square matrix with nonnegative coefficients such that every row sums to $1$. It is well known that $1$ is an eigenvalue every stochastic matrix, the complex ...
0
votes
0answers
28 views

Diagonalizablity of a substochastic matrix

Let D+E be a stochastic matrix i. e., D+E be the matrix with each row sum 1, where D and E are non-zero nonnegetive, irreducible matrices, I-D being non-singular. Can it be proved that D+kE is ...
1
vote
1answer
61 views

Spectral radius of a row-stochastic matrix plus a certain diagonal matrix

Conjecture: Let $A$ be a $4 \times 4$ row-stochastic, primitive matrix. Let $p_{i}$ be four probabilities such that $p_1 + p_2 + p_3 + p_4 = 1$. Let \begin{align} V &= \text{diag}_i\{p_{i + 1} + ...
1
vote
0answers
83 views

A “softmax”-like function for deciding on a partition

Softmax can be derived as follows. Say that we are given $k$ "log priors" $b_i$ that our data belongs to the $i$th category in some categorical distribution. Then we can solve for the category ...
1
vote
0answers
44 views

If $A$ and $B$ are transition matrices such that $||A-B|| < c$, then what can we say about $||A^n-B^n||$ for a given $n$?

Suppose there are two matrices, $A$ and $B$, that are both transition matrices for a Markov chain ($n\times n$, non-negative and row-stochastic). I know that A and B are "close" in the sense that $||A-...
1
vote
0answers
69 views

Proving that a doubly stochastic matrix is a convex combination of permutation matrices [duplicate]

This is a homework problem in my graph theory class and I wanted tips on how to solve it. Any tips would be appreciated.. Show that any doubly stochastic matrix is a convex combination of ...
1
vote
0answers
37 views

Proving that a matrix is nonnegative if its powers are nonnegative

I am working on a problem involving doubly stochastic matrices where I must prove that $P$ is doubly stochastic if and only if $P^k$ is doubly stochastic for $k = 1, 2, ...$ It is easy to show that if ...
0
votes
1answer
31 views

Does always a $B$ with orthonormal rows/column be found so that $BP=0$?

I am given, $P_{n\times n}$ column stochastic, I need to see whether a matrix of suitable order $B$ with an orthonormal column or rows can be constructed so that $BP=0$? I started trialing like this: ...
2
votes
2answers
306 views

Every finite state Markov chain has a stationary probability distribution

I am trying to understand the following proof that every finite-state Markov chain has a stationary distribution. The proof is from here. Let $P$ be the $k \times k$ (stochastic) transition ...
0
votes
1answer
50 views

tensor product of two column stochastic matrix [closed]

Is the tensor product of two column/row stochastic matrix is again a column/row stochastic? Thanks for helping.
1
vote
1answer
171 views

Perron Frobenius Theorem modified

On this site I found a modified version of Perron Frobenius Theorem Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then: 1 is an eigenvalue of multiplicity one. 1 is ...
1
vote
1answer
157 views

How many positive eigenvalues for a symmetric doubly stochastic matrix?

one interesting question is here about spectrum of symmetric doubly stochastic matrix. Given matrix $A\in R^{n \times n}$, which is a symmetric doubly stochastic matrix. and its spectrum is $\...
1
vote
0answers
16 views

Ordering in $\mathbb{R}^n$ and its representation in terms of stochastic matrix

Let $\mathbf{x},\mathbf{y} \in \mathbb{R}^n$. We say that $\mathbf{x} \leq \mathbf{y}$ iff $x_{(1)} \geq y_{(1)}, x_{(1)}+x_{(2)} \geq y_{(1)}+y_{(2)},\cdots,x_{(1)}+\cdots+x_{(n-1)} \geq y_{(1)}+\...
0
votes
2answers
117 views

Prove that : There exists a vector $x$ such that $Mx = x$ , where $M$ is a Markov matrix [closed]

Here's a proof that I found which looks pretty simple but I can't understand the last step. (A Markov matrix is a square matrix whose columns sum to one; $I$ is an identity matrix; $M^T$ and $I^T$ ...
1
vote
1answer
97 views

Maximum column sum of stochastic matrix

For a stochastic matrix $P$ of size $n$, we define $$\|P\|_1 := \max_{j \in [n]} \sum_{i \in [n]}|P(i,j)|$$ i.e., the maximum column sum, which is based on the $\|\cdot\|_1$ matrix norm. Now, ...
3
votes
1answer
208 views

Is the Birkhoff–von Neumann theorem true for infinite matrices?

The Birkhoff–von Neumann theorem states that every $n \times n$ doubly stochastic matrix is a convex combination of permutation matrices. Is this true for $\mathbb{N} \times \mathbb{N}$ matrices as ...
4
votes
1answer
274 views

Cesàro limit of a stochastic matrix

Let $A$ be a stochastic matrix. Then \begin{align*} \lim_{t \rightarrow\infty} A^t \end{align*} may not exist. For example: \begin{align*} A &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}...
2
votes
1answer
320 views

Examples of stochastic matrices that are also unitary?

In general there is no relationship between stochastic matrices and unitary matrices because they are used in different fields. The stochastic matrix presents all the non-negative elements with sum ...
2
votes
0answers
94 views

Decompose stochastic matrix in product of two stochastic matrices

There exist stochastic matrices $Q$ such that there is no stochastic matrix $P$ such that $P^2=Q$. I am interested in the following problem: For a given stochastic matrix $Q$, find stochastic ...
3
votes
2answers
638 views

Proving product of two column stochastic matrices is column stochastic (Proof verification)

For a matrix to be column stochastic we know $\sum_{i=1}^nA_{ij}=1$ for each column $j\in\{1,\ldots,n\}$. We have $$\sum_{j=1}^n (AB)_{ji} = \sum_{j=1}^n \sum_{k=1}^n A_{jk}B_{ki} = \sum_{j=1}^nA_{jk} ...
3
votes
2answers
3k views

Proving or disproving product of two stochastic matrices is stochastic

Let $P$ and $Q$ be two stochastic matrices. Does the product $PQ$ have to be stochastic? Prove or disprove. What Im thinking is that since matrix multiplication is only defined for two matrices $A$ ...
0
votes
2answers
82 views

Stochastic matrix question

A stochastic matrix is one which each column sum equal one. $$P= \begin{bmatrix} P_{11} & P_{12} & \ldots & P_{1N} \\ P_{21} & P_{22} & \ldots & P_{2N} \\ \ldots & \ldots ...
2
votes
1answer
150 views

Possible Jordan decompositions of stochastic matrices

Which are the possible Jordan normal forms for the stochastic matrices? For some reason I got the idea that they always consist of trivial $1\times 1$ blocks even if eigenvalues of multiplicity $>1$...
4
votes
1answer
813 views

When are the inverses of stochastic matrices also stochastic matrices?

A stochastic matrix, with elements $\in[0,1]$ and rows summing to 1 are known to have one eigenvalue 1 (stationary distribution) and the rest of lower magnitude. However I don't know about many ...
0
votes
1answer
77 views

What are Markov matrices and can they be used to model migration?

I have been looking at Markov matrices and have been having some difficulty getting my head around them. I was wondering if someone could explain to me in somewhat simple manners how they work. Also, ...
0
votes
1answer
2k views

Finding a limiting matrix

I am trying to find the limiting matrix for the indicated standard form. $$ \begin{matrix} 1 & 0 & 0 \\ .1 & .6 & .3 \\ .2 & .2 & .6 \\ ...