# 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.

187 questions
Filter by
Sorted by
Tagged with
20 views

### Maximum and minimum value of trace of unistochastic matrix

Let $P$ be a unistochastic matrix, that is, there exists a unitary matrix $U$ such that $P_{ij}=|U_{ij}|^2$. What is the maximum and minimum value of $\mathrm{Tr}[P]$? I'm also interested in the ...
• 21
36 views

67 views

### Spectral radius of a stochastic matrix

Let P be a irreducible stochastic matrix and Q be a matrix obtained by making one positive entry of P to be zero and remaining terms are same as P. If 1,t are the largest and second largest positive ...
16 views

### Trace-preserving map between stochastic matrices

Let $A$ be a stochastic matrix living in a tensor product space $W=V \otimes V \otimes \cdots \otimes V$ of dimension $d^N$, where $dim(V)=d$. In particular, $A$ is a left stochastic matrix, a real ...
• 21
1 vote
47 views

### solving ODE contain matrix

I am currently researching the specific image generation problem in this paper 'Score_Based Generative modeling through stochastic differential equation' At the end of page 14, the authors are using ...
• 11
28 views

### What are the eigenvalues of this matrix-valued equation?

In the following, let $P$ be a stochastic matrix, i.e. $\sum_{j} P_{ij} = 1, P_{ij} \geq 0.$ Assume furthermore $P$ is irreducible and aperiodic, which implies there is a unique stationary ...
• 1,494
115 views

### Deficiency of unit eigenvalues in a stochastic matrix

Statement Let $A\in\mathbb{R}^{m\times m}$ be a (row) stochastic matrix. It is known that the eigenvalues of such matrix lies in the complex unit disk. Now I am only interested in the eigenvalues ...
• 129
47 views

### How would you find stationary distribution for the Markov chain defined by astochastic matrix? [closed]

I'm not really sure how to find the stationary distribution for the matrix $P_1$. I've tried Gaussian elimination but that doesn't seem to work. I've also tried converting it into a system of ...
1 vote
32 views

### Second largest eigenvalue of product of two stochastic matrices

Suppose I have two stochastic matrices $A_1$ and $A_2$. It is well known that the convergence rate of the Markovian chain generated by a stochastic matrix is determined by the absolute value of its ...
• 917
13 views

### Two non convex optimization problems to find a stochastic matrix and a probability. And to implement a numerical solution with Python

I would like to present you two non-convex (so far) optimization problems. My goal is to implement a numerical solution with Python. I'm keen to do some maths if it makes the problems easier to solve ...
43 views

### Efficiently obtain matrix from majorization

Let $x,y\in\mathbb{R}^n$, with $x_1\geq x_2\geq...\geq x_n$, $y_1\geq y_2\geq\ldots,y_n$. Say that $x$ majorizes $y$ if $\sum_{i=1}^{k}x_i\geq\sum_{i=1}^{k}y_i$ for $k=1,2,\ldots,n$, with equality ...
• 136
53 views

### Proving two probability matrix multiplication is still a probability matrix

There is a n by n probability matrix $Q = Q_{ij}$ and $Q_{ij} \ge 0 \quad(i, j = 1,2,...,n)$ with $\sum_{j=1}^nQ_{ij} = 1 \quad (j = 1,2,...,n)$. I am curious about how to prove that $Q^2 = QQ$ is ...
• 287
31 views

### Proving probability vector and matrix holds as markov matrix after multiplication

There is a n by n probability matrix $Q = Q_{ij}$ and $Q_{ij} \ge 0 \quad(i, j = 1,2,...,n)$ with $\sum_{j=1}^nQ_{ij} = 1 \quad (j = 1,2,...,n)$. Furthermore, there is a probability vector p = $p_i$ ...
• 287
1 vote
62 views

### Finding general solution for Markov Matrix Eigenvalues.

I am being asked to solve a Markov Matrix in general terms. Essentially I need to prove an eigenvalue with always be $1$. I have set up the following matrix: \begin{pmatrix}p&1-p\\q&1-q\end{...
• 21
219 views

### Deducing the powers of a Markov matrix

I have a Markov matrix that looks like this: \begin{align} P = \begin{pmatrix} 1 - p && q \\ p && 1 - q \end{pmatrix} \end{align} Now, I want to prove that the following formula by ...
• 287
36 views

### "Height" of the positive eigenvector of a non negative irreducible symmetric stochastic banded Toeplitz matrix

Let $(a_n)$ be a sequence of non-negative real numbers such that $\sum_{i = 0 }^\infty a_i = 1$. We assume that only a finite numbers of the $a_i$s are non zero. Let $M_d$ be the $d \times d$ ...
• 11
62 views

### Derive property of solutions linear equations from matrices

My question concerns the following systems of linear equations: $x = 1 + Ax$ and $y = 1 + By$, where 1 denotes the $n$x1 vector of 1's and $A$ and $B$ are $n$x$n$ substochastic matrices that satisfy ...
144 views

### The permutation matrices are the doubly stochastic matrices with the highest Frobenius norm

In a 2013 talk, Alexandre d'Aspremont did claim the following: Among all doubly stochastic matrices, the rotations, hence, the permutation matrices, have the highest Frobenius norm I had never ...
1 vote
99 views

### Prove that a column stochastic matrix can't have an eigenvalue equal to -1. Is this proof correct? If not, how to fix it?

The definition of an eigenvalue: $$x * A = E * x$$ where $E$ is an eigenvalue, $A$ is a matrix and $x$ is a vector $≠ 0$. My proof: Let's assume that $E = -1$. Then $A * x = -x$. Adding $x$ to both ...
67 views

214 views

### Series of polynomials very nearly follows binomial coefficients but doesn't quite

I'm modelling a system using a Markov chain and by a few iterations of the transition matrix I can see a pattern emerging in the resulting polynomial that really looks like Pascal's triangle, but isn'...
173 views

### Given an $n\times n$ irreducible stochastic matrix $P$, how to prove that ${\rm rank}(I-P)=n-1$?

I want to prove that ${\rm rank}(I-P)=n-1$, and I know that $I-P$ is not full rank, all columns add to be $0$ I want to prove stationary distribution $\pi$ is unique by this so please don't prove it ...
• 425
58 views

### Variance of random matrix?

Let's say $W$ is a symmetric matrix random variable, i.e., $W=W_{ij}$ with probability $P_{ij}$. We already know the definition of $\mathbf{E}[W]$. Is there a definition for $\mathbf{Var}[W]$? And ...
57 views

### How can block-matrices be irreducible?

Suppose we define two matrices P1 and P2 as follows: both are 2x2 matrices both have strictly positive entries And then we define P to be a 4x4 transition matrix of the form P = [P1 0] [0 P2] It'...
• 115
93 views

### How do we prove that Stochastic matrices preserve l1 norm?

I have tried some previously answered questions on the forum but I don't see a formal proof anywhere. I can't understand where to begin either. Essentially given that $A$ is a stochastic matrix and $b$...
42 views

### Transform a rank-$N$ matrix to a double stochastic matrix without any iterative algorithms?

Is there a way to take a general $N \times N$ matrix $Y$, and turn it into a double stochastic matrix $X$ analytically? With any iterative algorithms? Ans: The Sinkhorn algorithm does that, but ...
• 5,899
1 vote
105 views

### Number of positive and zero entries in doubly stochastic matrices

I have been researching doubly stochastic matrix properties, but didn't find proof of pretty known fact, so I would like to ask it here. How to prove the following? A doubly stochastic matrix Cannot ...
• 101
1 vote
47 views

### Optimization problem on stochastic matrices

A matrix $A \in \mathbb{R}^{m \times n}$ is a stochastic matrix if $A \in [0, 1]^{m \times n}$ and $\sum_j A_{ij} = 1, \forall i \in [n]$. Let $\mathcal{S_{m, n}}$ be the set of $m \times n$ ...
• 1,802
90 views

### Why are eigenvectors of Matrices orthogonal to the vector 1

For transposes of Markov matrices we have eigenvalue $\lambda = 1$ with eigenvector $\vec{1}$. According to my professor, all eigenvectors with eigenvalue other than 1 of the Markov matrix must be ...
163 views

### Sum over rows and columns of double stochastic matrix

I have the following $2m \times 2m$ matrix $$\tilde{P}((u,v), (x,y)) = \begin{cases} \frac{1}{d_v -1}, & \text{if } v=x ~\text{and}~ y\neq u \\ 0 & \text{otherwise } \end{cases}$$ ...
• 863
399 views

### Does PageRank imply that eigenvalue one exists for any matrix?

I learned from this lecture that for the PageRank algorithm the following equation holds: $$r^{i+1}=L r^{i}$$ I thought when the $r$ vector converges $r^{i+1}=r^{i}$, and hence the equation would ...
• 724
1 vote
47 views

### Bound of the permanent of a stochastic matrix

Given a stochastic matrix $A \in [0, 1]^{n \times n}$, we want to have a bound of its permanent $\operatorname{per}(A)$. We do not want a general bound like that for the permanent of a doubly ...
• 1,802
135 views

### Are tridiagonal stochastic matrices irreducible?

According to Wikipedia, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal and the supradiagonal. To my understanding, in a tridiagonal ...
• 55
263 views

### Prove that for the eigenvector corresponding to the eigenvalue $1$, the components sum up to $1$

I had a hard time proving fact 6 in this article: If $A$ is a positive column-stochastic matrix, then there is a unique eigenvector corresponding to the eigenvalue $z = 1$ such that it has only ...
• 55
102 views

### The second smallest eigenvalue of $P^T(I-ee^T)P$?

I have a problem when I deal with a transition matrix question. To explain it briefly, my problem is whether the second smallest eigenvalue of $P^T(I-ee^T)P$ is not less than $1$, where $P$ is a ...
• 31
194 views

### Doubly stochastic matrix

Prove that Markov chain will be irreducible if its transition matrix is doubly stochastic. I was told to use Birkhoff's theorem, but I don't know how to use it at all.
• 367
400 views

### How to find probability of ending up in a row of a stochastic matrix?

I'm solving a programming problem which (after a small modification) turned out that can be represented as a stochastic matrix. One example is:  \begin{bmatrix} 0 & \frac{1}{2} & 0 & 0 &...
• 231
1 vote
58 views

### Find the result of T given matrices against ordered basises

I am trying to solve this problem: Consider in $\mathbb{R}^2$ the ordered basis $v_1 = (1, 3)$, $v_2 = (2, 5)$. Let $T : \mathbb{R}^2 \to \mathbb{R}^2$ be a linear image with as the matrix with ...
46 views

### Showing a stochastic matrix transforms any vector into a vector with a smaller (or equal) sum of absolute value of components

The problem is from David Lay's textbook in linear algebra: If $A$ is an $m\times m$ stochastic matrix, and $A\vec{x} = \vec{y}$, show that $|y_1| + ... + |y_m| \leq |x_1| + ... + |x_m|$. First, since ...
100 views

### Relationship between the diagonal elements of a Hermitian matrix and its eigenvalues

CONVEX AND CONCAVE FUNCTIONS OF SINGULAR VALUES OF MATRIX SUMS This question comes from the proof of theorem $1$ linked above. Assume $A,B,C=A+B$ are $n\times n$ Hermitian positive semidefinite ...
• 1,076
76 views

### What is the minimal formal structure required to define a stochastic matrix

A stochastic matrix is often defined as a square matrix $[S_{ij}]$, such that the rows (or columns, depending on the convention) sum to 1. The rationale behind this definition is to think about each ...
• 155
1 vote
69 views

### Generalized Stochastic Matrices with Negative Transition Probabilities

Consider a square matrix $A$ with the property $\sum_j A_{ij}=1$ for all $i$. That is, I've relaxed the positive element requirement for a (right) stochastic matrix. What properties do these matrices ...
• 109
Say we have two random variables $X$, $Y$. They are discrete variables (or discretization of continuous variables), both with $k$ categories. Define the left stochastic matrix as \$P(X|Y)_{ij}:=p(x_i|...