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
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 ...
ytaguchi's user avatar
0 votes
1 answer
36 views

Eigenvectors of a square stochastic matrix

I was reading the following lecture: https://www.stat.cmu.edu/~cshalizi/statcomp/13/lectures/15/markov.pdf, but I had a problem with a certain paragraph which is this: Since q is a square, $K \times ...
Ghanem's user avatar
  • 23
1 vote
1 answer
52 views

Formulation of a state transition matrix

My transition matrix differs from that provided by the author. As this problem is part of my homework I would appreciate some help to see why my solution doesn't work. This is exercise 17-29 from the ...
jh1356's user avatar
  • 85
0 votes
1 answer
51 views

Does the invariant distribution depend on the initial distribution of a Markov Chain?

I have just learnt about the invariant distribution, and was wondering if such depends on the initial distribution of a Markov chain in anyway, and if so, whether the following is the correct ...
Princess Mia's user avatar
  • 2,321
0 votes
0 answers
21 views

Proposed analysis techniques - optimal decision given expectation

I am going to conduct an analysis in order to "weight" different possibilities of actions in a given market. I have an overall level of effort that can be distributed accross the different ...
Mathman's user avatar
  • 11
0 votes
0 answers
38 views

The 2-norm of matrix of a matrix (related to the second-largest singular value)

I am seeking assistance in investigating the following result. Assume matrix $A \in \mathbb{R}^{n \times n}$ a nonnegative, irreducible and row-stochastic matrix. I wonder if the 2-norm $\|(I_n - \...
littlepepper's user avatar
0 votes
0 answers
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 ...
Haritha Cheriyath's user avatar
0 votes
0 answers
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 ...
Philap's user avatar
  • 21
1 vote
1 answer
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 ...
Duc Toan's user avatar
0 votes
0 answers
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 ...
a_student's user avatar
  • 1,494
0 votes
3 answers
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 ...
Rami Zouari's user avatar
0 votes
1 answer
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 ...
Oliver Nielsen's user avatar
1 vote
0 answers
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 ...
poisson's user avatar
  • 917
0 votes
0 answers
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 ...
user806923's user avatar
2 votes
0 answers
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 ...
NDB's user avatar
  • 136
0 votes
1 answer
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 ...
Sonamu's user avatar
  • 287
0 votes
0 answers
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$ ...
Sonamu's user avatar
  • 287
1 vote
1 answer
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{...
Dogjus's user avatar
  • 21
2 votes
2 answers
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 ...
Sonamu's user avatar
  • 287
0 votes
0 answers
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$ ...
Nathan's user avatar
  • 11
0 votes
0 answers
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 ...
user675763's user avatar
4 votes
1 answer
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 ...
Rodrigo de Azevedo's user avatar
1 vote
1 answer
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 ...
HEISENBERG9871's user avatar
0 votes
0 answers
67 views

Spectral norm of a symmetric strictly stochastic matrix on simple random walk

I am considering the spectral norm of a transition matrix on simple random walk om $\mathbb{Z}^2$ as follows. Let $S_n$ be a simple random walk on $\mathbb{Z}^2$. Let $D$ be a connected subset of $\...
Hoai Nhan 2171 Le's user avatar
0 votes
0 answers
136 views

Doubly stochastic matrix in Markov and distributions

The transition matrix $\bf P$ of a Markov chain be a doubly stochastic matrix that is all entries are non-negative and all row sums as well as all column sums are equal to $1$. How can I prove that ...
sneha_jerin's user avatar
0 votes
0 answers
88 views

Birkhoff polytope vs permutation polyhedron

I cannot understand a few things about the Birkhoff polytope. The Birkhoff polytope is defined as a polyhedron of all $n \times n$ doubly stochastic matrices. How is is it polytope then? To transform ...
kain's user avatar
  • 1
0 votes
2 answers
69 views

What are the conditions for a non-Hermitian matric's Rayleigh quotient to be less than its maximum eigenvalue?

What I am trying to prove is that: for a row-stochastic matrix P (not necessarily symmetric), whose every row sums $\sum_{j=1}^nP_{ij}=1$, the Rayleigh quotient of P, $R(\mathbf{x})=\frac{\mathbf{x}^{\...
Zhengyang Lin's user avatar
5 votes
1 answer
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'...
Justin Booth's user avatar
0 votes
0 answers
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 ...
Gang men's user avatar
  • 425
0 votes
0 answers
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 ...
Minh Lê's user avatar
0 votes
1 answer
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'...
mr. man's user avatar
  • 115
0 votes
1 answer
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$...
Vishakha Lall's user avatar
2 votes
0 answers
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 ...
wonderich's user avatar
  • 5,899
1 vote
1 answer
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 ...
nezudem's user avatar
  • 101
1 vote
0 answers
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$ ...
Vezen BU's user avatar
  • 1,802
0 votes
1 answer
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 ...
Matt Wise's user avatar
2 votes
1 answer
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}$$ ...
Thoth's user avatar
  • 863
4 votes
4 answers
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 ...
Lerner Zhang's user avatar
1 vote
0 answers
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 ...
Vezen BU's user avatar
  • 1,802
0 votes
1 answer
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 ...
Jack's user avatar
  • 55
0 votes
1 answer
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 ...
Jack's user avatar
  • 55
3 votes
0 answers
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 ...
Rexdu's user avatar
  • 31
0 votes
0 answers
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.
Marja's user avatar
  • 367
2 votes
1 answer
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 &...
Hi-Angel's user avatar
  • 231
1 vote
2 answers
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 ...
fatCat9999's user avatar
0 votes
1 answer
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 ...
doctorpigeonhole's user avatar
0 votes
1 answer
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 ...
fusheng's user avatar
  • 1,076
2 votes
1 answer
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 ...
Kiah's user avatar
  • 155
1 vote
1 answer
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 ...
Jake's user avatar
  • 109
2 votes
0 answers
45 views

Conditions for the invertibility of a left stochastic matrix.

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|...
Mingzhou Liu's user avatar