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
0 answers
70 views

Confusion in one statement related to the Birkhoff polytope

I know that the set of doubly stochastic matrices $(\Omega(n))$ form a polyhedron. I only know about polyhedron is that it is a $3$-dimensional shape with flat polygonal faces, straight edges and ...
user avatar
1 vote
1 answer
57 views

State Transition Matrix

A similar question to this post, but now row sums are zeros. I don't think the suggeted approach in the comment works anymore. Given $$\dot x = A(t)x(t)$$ where $A(t)$ is a Metzler matrix whose row ...
user avatar
0 votes
0 answers
60 views

State Transition Matrix of a time varying linear dynamical system

Given $$\dot x = A(t)x(t)$$ where $A(t)$ is a Metzler matrix whose column sums are zeros at all time $t$, prove that the state transition matrix of the system is a left (or right) stochastic matrix ...
user avatar
1 vote
1 answer
72 views

Prove that a matrix can be written as a sum of permutation matrices

Given a square matrix $A$ of size $n$ whose entries are non-negative integers and where the sum of each column and row is equal to $k$, prove that $A$ can be written as a sum of $k$ permutation ...
user avatar
0 votes
0 answers
79 views

Proving this matrix limit

Let $A$ be a stochastic matrix. Prove that $$\lim_{k\to\infty}\frac{1}{k}\sum^{k-1}_{i=0}A^i$$ exists. This is my attempt. Let $$T^{-1}AT = \begin{bmatrix} A_1 & 0 & 0 \\ 0 &...
user avatar
  • 503
0 votes
2 answers
84 views

Eigenvalues of this stochastic matrix

Consider the matrix $I - P + Q$, where $P$ and $Q$ stochastic matrices that satisfy $$PQ = QP = QQ = Q$$ I want to show that $I - P + Q$ is invertible, so I am analyzing its eigenvalues. I know that ...
user avatar
  • 503
0 votes
0 answers
6 views

I want to show that the multiplication of $y_0 $by $V(\Theta-\epsilon I)$ shrink the variance of $y_0$ more than the multiplication by $V(\Theta)$

Say I have the following row stochastic matrix $V(\Theta)=(I-(I-\Theta)W)^{-1} \Theta$ where $W$ is a row stochastic element-wise nonzero matrix and $\Theta$ is a diagonal matrix with elements less ...
user avatar
0 votes
2 answers
63 views

Does there exist a stochastic matrix $P$ such that $\ker(P-I)$ contains no nonnegative vector?

In the proof of the existence and uniqueness of a stationary distribution of a finite-state discrete Markov chain I came across the construction of a distribution vector $v \in \mathbb{R}^n$ with $v = ...
user avatar
  • 356
0 votes
1 answer
28 views

Must the matrix in the product be right-stochastic?

Let $A$ be a square right-stochastic matrix, so that $A$ has nonnegative entries and each row sums to unity. For an invertible square matrix $B$, the product $A B$ is also right-stochastic. Must it be ...
user avatar
0 votes
0 answers
18 views

Decomposition of stochastic matrices into tridiagonal ones

I was wondering if some results were known for the following problem for which I couldn't find any information, except for this similar question that unfortunately doesn't have answers. So let's start ...
user avatar
  • 31
1 vote
1 answer
88 views

Diagonalisation of stochastic matrices

Suppose that $(X_n)_{n≥0}$ is a Markov chain on a state space $I = {1, 2}$ and stochastic matrix $$P = \begin{bmatrix} \frac{1}{4} & \frac{3}{4} \\ \frac{1}{3} & \frac{2}{3} \end{bmatrix}$$ (a)...
user avatar
2 votes
1 answer
26 views

What justifies this equality?

Suppose $P$ is a stochastic matrix with equal rows, with $P_{ij}=p_j$. By induction on $n$, $$P_{ij}^n=\sum_k P_{ik}^{n-1}P_{kj}=\sum_k p_k p_j=p_j$$ What happens in the second equality? What ...
user avatar
  • 57
0 votes
1 answer
42 views

Selecting a strictly positive permutation from a stochastic matrix

This question is related to another one I recently posed. I am posting this new question because (i) trying to prove that other conjecture seems to have been quite fruitless so far; and (ii) the ...
user avatar
2 votes
1 answer
100 views

Finding a strictly positive “good” permutation in a doubly stochastic matrix

Let $n$ be a positive integer and $\mathbf X\equiv[x_{ij}]_{i=1,j=1}^{i=n,j=n}$ a doubly stochastic matrix; that is, a matrix with non-negative elements such that the sum of every row and the sum of ...
user avatar
0 votes
1 answer
82 views

Rank of a stochastic matrix $+$ the identity matrix?

I have a row-stochastic matrix $G\in \mathbb{R}^{n\times m}$, such that $n<m$ and $Rank(G)<n.$ Define $J\in \mathbb{R}^{n\times m}$ as follows. $$ J_{i,j} = \begin{cases} 1 & i=j,i\in [n]\\ ...
user avatar
0 votes
1 answer
46 views

For reversible Markov chains larger off diagonal elements imply smaller eigenvalues

The following is claimed in Remark 3.1 in this paper (page 6). Let $M$ and $M'$ be $\pi$-reversible Markov chains on $X$ with eigenvalues $1=\lambda_0 \ge \lambda_1 \ge \cdots \ge \lambda_{|X|-1}$ and ...
user avatar
0 votes
0 answers
15 views

Are there any good results characterizing the difference in stochastic matrices?

We frequently use stochastic matrices $P$ in various settings (for example, MDPs). In practice, we estimate stochastic matrices using observed samples and arrive at an estimate $P_0$. Usually there is ...
user avatar
  • 959
1 vote
0 answers
55 views

Eigenvectors of Stochastic Matrix

Let $N\in\mathbb{N}$. Define the matrix $Q\in\mathbb{R}^{(N+1)\times(N+1)}$ by $$Q_{ij}=\binom{N}{j}\Big(\frac{i}{N}\Big)^j\Big(1-\frac{i}{N}\Big)^{N-j}$$ for all $0\le i,j\le N$. The sum of each row ...
user avatar
  • 364
1 vote
1 answer
95 views

Power of Stochastic Matrix

Given the stochastic matrix $$Q = \begin{pmatrix}0&2/3&1/3\\1/3&0&2/3\\2/3&1/3&0\\\end{pmatrix}\in \mathbb{R}^{3\times3}$$ I wish to compute $Q_{1,1}^n$ (the entry in the first ...
user avatar
  • 364
2 votes
2 answers
89 views

Finding a pair of commutative stochastic $3 \times 3$ matrices

Could you please give me an example of a pair $\left(A,B\right)$ of commutative stochastic $3 \times 3$ matrices with real entries given $A \neq B$ and excluding the identity matrix, symmetric ...
user avatar
2 votes
1 answer
31 views

Why doesn't detailed balance always imply a uniform distribution for Markov Chains?

Consider a state (row) vector $\{\pi_i\}$ and a right-stochastic matrix $P_{ij}$. To calculate the next state vector $\pi'$ you can right-multiply by $P$: $$\pi'_i=\sum_j \pi_jP_{ji}$$ Detailed ...
user avatar
0 votes
0 answers
42 views

Can we approximate the linear sum assignment solution with bistochastic matrices?

This question was concerned with random bistochastic matrices and the answer pointed out an algorithm, that can "bistochastize" a starting matrix $\boldsymbol{X}$ (with positive elements ...
user avatar
  • 133
3 votes
0 answers
79 views

Equality of weighted norm of matrix columns

Consider a stochastic matrix $A=(a_{i,j})_{i,j=1}^n$ and $\omega$ its normalized left-eigenvector to the eigenvalue $1$. Define $|.|_{\omega}$ as $|x|_{\omega}=\sum_{i=1}^n|x_i|\omega_i$. For fixed $i\...
user avatar
  • 955
0 votes
1 answer
47 views

How does one get $M^Ts=s$ from $M$ being stochastic and symmetric w.r.t some scalar product?

Let $M \in \mathbb R_+^{N,N}$ be a nonnegative stochastic matrix and symmetric w.r.t some scalar product $\langle \cdot \, \vert \, \cdot \rangle_s$ given by some positive vector $s \in \mathbb R_*^{N}...
user avatar
  • 1,255
0 votes
1 answer
41 views

How can I make sense of this Matrix inequality?

In https://tel.archives-ouvertes.fr/tel-02926037/document one page 35 the following Lemma is stated: Lemma I.5: Let $M \in (\Bbb R^+)^{N \times N}$ be a stochastic matrix. Then for any positive ...
user avatar
  • 1,255
2 votes
0 answers
39 views

Interpretation of the Sinkhorn-Knopp algorithm applied to a (singly stochastic) transition matrix of a Markov process?

Say I have a discrete-time Markov process (and let's say discrete states too, for simplicity). If $\mathbf p_t$ is a vector of probabilities over states at time $t$, then the probability distribution ...
user avatar
  • 289
0 votes
2 answers
33 views

Factors of a stochastic matrix [closed]

If $A B = C$ where matrix $C$ is stochastic (all entries are positive and all rows add to $1$) then is it necessary that both $A$ and $B$ be stochastic?
user avatar
0 votes
1 answer
58 views

Eigenvalues of a 2x2 stochastic Matrix

In one of my lecture notes it is stated that one of the Eigenvalues (EV) of a stochastic Matrix can be calculated by $P_{11} - P_{21}$ I.e I have the following matrix : $$\begin{matrix} 0.1 & ...
user avatar
1 vote
0 answers
82 views

Birkhoff-von Neumann Theorem

I am reading from Linear Algebra in Action by Dym and am working through the proof of the BvN Theorem. For the sake of clarity, ill write up everything until the point where I get lost. Theorem: Let $...
user avatar
1 vote
0 answers
30 views

Problems with eigendecomposition of a big stochastic matrix

I face the following problem. I generate a big $1202 \times 1202$ stochastic matrix $Q$ whose columns adds to $1$ (up to numeric precision). The elements of $Q$ are in $[0,1]$. I use the ...
user avatar
2 votes
0 answers
73 views

For a stochastic row matrix $A$, invertibility of $I-A$

Consider a Markov process $X_t$ where $t$ belongs to natural numbers, which takes values on a finite state space $\mathcal{X}$. We say that $x \in \mathcal{X}$ is an absorbing state if $X_t = x$ ...
user avatar
0 votes
1 answer
103 views

Second-largest singular value of a row-stochastic matrix

I am working on this problem. Consider a non-singular row-stochastic matrix $A$; we know that its 2-norm, $\|A\|_2$, is strictly greater than one if and only if it is not doubly stochastic. Let $\...
user avatar
  • 93
0 votes
1 answer
86 views

Irreducible finite Markov chain and its stochastic matrix

Let $P$ be a stochastic matrix on a finite set $I$. Show that a distribution $\pi$ is invariant for $P$ if and only if $\pi(I-P+A)=a$, where $A=(a_{ij}:i,j\in I)$ with $a_{ij}=1$ for all $i$ and $j$, ...
user avatar
3 votes
0 answers
34 views

full rank by inspection

I have an $n\times n$ matrix where each row is a probability vector. In the $2\times 2$ case, the matrix has full rank so long as the two rows differ. I wonder whether for $n \geq 3$ there is still ...
user avatar
  • 53
0 votes
2 answers
140 views

Infinite power of doubly stochastic matrix without using diagonalization

Given $$M := \frac17 \begin{bmatrix} 3 & 1 & 1 & 1 & 1 \\ 1 & 3 & 1 & 1 & 1 \\ 1 & 1 & 3 & 1 & 1 \\ 1 & 1 & 1 & 3 & 1 \\ 1 & 1 & ...
user avatar
0 votes
0 answers
525 views

Finding stable distribution of a Stochastic Matrix

so im currently looking at Markov diagrams and stochastic matrices and have become quite stuck on some parts of this question below and was looking for some help. Here is what I have done so far, For ...
user avatar
  • 349
0 votes
0 answers
22 views

What's the application of doubly-stochastic matrices in engineering?

Today I learned the existence of such matrix . wolframe This is indeed a very interesting thing. I am wondering if there is any realworld application of such matrix. It seems that this matrix has ...
user avatar
1 vote
0 answers
88 views

Conditions under which a row-stochastic Markov matrix has positive eigenvalues

Let $A \in \mathbb{R}_+^{n\times n}$ be the adjacency matrix of a weighted directed graph, i.e., $A$ is nonsymmetric and with nonnegative entries. Let $M = D^{-1}A$ be the row-stochastic Markov matrix ...
user avatar
1 vote
2 answers
855 views

Proving a specific eigenvalue of a 6x6 Matrix.

Currently, I am looking at Markov diagrams and their associated transition matrices. I am trying to prove that the transition matrix has eigenvalue $\lambda=1$. I am aware that to find the eigenvalues ...
user avatar
  • 349
3 votes
1 answer
1k views

Determinant of a 6x6 matrix

There's this part of my assignment which involves stochastic matrices and i've done most parts of it but there's one part which requires me to show that its eigenvalue is 1. The only way i can think ...
user avatar
2 votes
1 answer
128 views

Raising non-diagonalizable Markov transition matrix to the power of $n$

Consider an aperiodic and irreproducible Markov process with absorbing states. For each non-absorbing state, how can I numerically compute the likelihood of ending up in each absorbing state? Assume ...
user avatar
  • 123
8 votes
0 answers
301 views

Is there any significance to this "doubly stochastic matrix" with both a discrete and continuous index?

This is just idle curiosity. Consider the function $(\lambda, n) \mapsto e^{-\lambda} \frac{\lambda^n}{n!}$, where $\lambda \in \mathbb{R}_{\ge 0}$ is a nonnegative real parameter and $n \in \mathbb{Z}...
user avatar
1 vote
1 answer
46 views

$I-M$ is an non-invertible matrix

Why if $M = (m_{ij})$, with dimension $n \times n$, is a stochastic matrix, then the matrix $I-M$ must be non-invertible? I think if we echelon $I-M$, then eventually we will get a zero line (i.e. $\...
user avatar
  • 135
0 votes
1 answer
53 views

Eigenvalues of a diagonalizable stochastic matrix

Suppose $T$ is a stochastic diagonalizable matrix. Then we can write $T\cdot 1=P^{-1}DP\cdot 1=1$ where $1$ is the column vector with all entries equal to one. Then we have $DP\cdot 1=P\cdot 1$ where $...
user avatar
0 votes
1 answer
112 views

Decomposition of a stochastic matrix

Let $T$ be a square row (not doubly) stochastic matrix. Assume that $T$ is diagonalizable. Then write $T$ as $P^{-1}DP$. Consider now the matrices $D_1=P^{-1}D^{\frac{1}{2}}P$ and $D_2=P^{-1}D^{\frac{...
user avatar
0 votes
1 answer
246 views

Convergence of Markov Chains

I have stumbled upon Markov chains respectively finite stochastic matrices (gladly it didn't hurt too much). There is this theorem on the existence of stationary distributions which is standard: Let P ...
user avatar
1 vote
0 answers
92 views

Eigenvalues of Markov matrix

I was trying to prove that a Markov matrix always has an eigenvalue 1 but I seem to have proved that all eigenvalues of a Markov matrix are equal to one! Could anyone look at my work and point out the ...
user avatar
1 vote
1 answer
133 views

Can we find a stochastic matrix $Q$ such that $M = \frac{1}{C} \sum_{i=1}^C Q^i$ where $M$ is a stochastic matrix?

Given a stochastic matrix $M$, can we always find another stochastic matrix $Q$ such that $M$ can be written by the mean of a geometric sum $M = \frac{1}{C} \sum_{i=1}^C Q^i$ for any $C > 1$? My ...
user avatar
  • 125
1 vote
1 answer
143 views

Uniform distribution on the space of stochastic matrices

Does there exist any uniform distribution on the space of (right) stochastic matrices (a real square matrix, with each row summing to 1)? If so, is it unique? Besides the uniform distribution, does ...
user avatar
  • 125
0 votes
1 answer
69 views

Stochastic matrix and eigenvector as rational function of its elements.

Consider stochastic matrix $P$, it means that the sum of elements in row is equal $1$. Matrix $P$ is function of $p\in\left(0,1\right)$, it means that $$P=\begin{pmatrix}f_1(p) & f_2(p) & f_3(...
user avatar
  • 519