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
1answer
42 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}...
0
votes
1answer
40 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 ...
2
votes
0answers
24 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 ...
0
votes
2answers
27 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?
0
votes
1answer
25 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 & ...
1
vote
0answers
47 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 $...
1
vote
0answers
28 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 ...
2
votes
0answers
61 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$ ...
0
votes
1answer
52 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 $\...
0
votes
1answer
31 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$, ...
3
votes
0answers
24 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 ...
0
votes
2answers
84 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 & ...
0
votes
0answers
300 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 ...
0
votes
0answers
18 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 ...
1
vote
0answers
79 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 ...
1
vote
2answers
360 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 ...
3
votes
1answer
787 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 ...
2
votes
1answer
53 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 ...
8
votes
0answers
185 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}...
1
vote
1answer
28 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. $\...
0
votes
1answer
31 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 $...
0
votes
1answer
59 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{...
0
votes
0answers
29 views

Comparison norm of a vector and multiply a stochastic matrix by that vector.

Let $S \in \mathbb{R}^{n \times m}$ a column stochastic matrix (i.e. a matrix with non-negative components whose columns sum to one), and $R \in \mathbb{R}^{n \times m}$ be a row stochastic matrix. ...
0
votes
1answer
88 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 ...
1
vote
0answers
52 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 ...
1
vote
1answer
77 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 ...
1
vote
1answer
75 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 ...
0
votes
1answer
51 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(...
5
votes
0answers
94 views

What's this matrix transformation called?

Given an augmented matrix $$M = [A \mid X] = \left[\begin{array}{cc|c} a & b & x\\ c & d & y \end{array}\right],$$ there's an associated augmented matrix defined like so $$M' = ...
1
vote
1answer
67 views

Proving that $\det(I-T_i) >0$ where $T$ is a primitive stochastic matrix and $T_i$ is a principal submatrix

Let $T$ be an $n \times n$ row-stochastic matrix which is primitive (i.e. there is a positive integer $k$ such that all entries of $T^k$ are strictly positive). Let $T_i$ denote the matrix obtained by ...
0
votes
1answer
33 views

Left eigenvector for eigenvalue < 1 for a square stochastic matrix: coordinates of eigenvector sum to zero.

If $v$ is a left eigenvector of stochastic matrix $P$ with $vP = \lambda v$ for $\lambda <1$, can you show that $\sum_{i = 1}^{N} v_{i} = 0$. You can assume that $v$ is normalized.
3
votes
2answers
115 views

Decomposition of doubly stochastic matrices

Suppose $A$ is a doubly stochastic matrix, that is each row and column have the sum of their entries as $1$ and the entries are all nonnegative. Now, suppose $A=BC$ where $B$ is idempotent and $C$ is ...
0
votes
0answers
20 views

Stochastic matrices for continuous-time linear systems

If matrices are stochastic (row stochastic) or doubly/bistochastic, we can make claims about the behavior of the discrete-time dynamical systems they represent. For example: discrete-time Markov ...
0
votes
1answer
122 views

Diagonal of (self) product of doubly stochastic transition matrix

By doubly stochastic and transition, I mean each row sum and column sum of a matrix is 1 and each element of the matrix is in [0, 1]. Here, I am considering the matrix is n by n where n is finite. I'...
0
votes
0answers
36 views

The inverse of stochastic matrices, how to classify them?

Stochastic matrices $\bf P$ with element $p_{i,j}$ at row $i$ and column $j$ have some specific limitations to them, namely: $$\cases{\displaystyle\sum_{\forall j} p_{i,j} = 1\\ p_{i_j} \geq 0}$$ Is ...
1
vote
1answer
190 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
50 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
27 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
85 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
312 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
103 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
1answer
24 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
54 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 ...
1
vote
0answers
49 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
821 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) ...
2
votes
2answers
66 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^...
1
vote
0answers
83 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
83 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
41 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
60 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}&...