Skip to main content

Questions tagged [nonnegative-matrices]

A non-negative matrix is one whose entries are non-negative.

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

stability of rank one perturbation of stochastic matrix

Let $I$ be the identity matrix and $P$ be an irreducible $n$ by $n$ row stochastic matrix. Let $d$ be a stochastic (column) vector and $e$ be an all one (column) vector. Let $t > 0$ be a real ...
AlphaRL's user avatar
  • 175
2 votes
1 answer
22 views

Eigenvalues of the product of a stochastic matrix and a doubly stochastic matrix

I am playing with compositions of finite state Markov chains and have this product matrix $P=AB$, where $A$ is a stochastic matrix (rows sum to 1) and $B$ is a doubly stochastic matrix. Moreover, $B$ ...
Kryvtsov's user avatar
  • 151
1 vote
0 answers
35 views

Optimal transition matrix that minimizes mixing time

For a finite state space, say I have a transition matrix $P$ such that it is irreducible and aperiodic. The stationary distribution is $\pi$. I wonder if there's any literature on how to pick an extra ...
Kryvtsov's user avatar
  • 151
2 votes
0 answers
32 views

Change of basis to a nonnegative matrix

Let $A$ be an arbitrary symmetric, square matrix. I would like to use the Perron-Frobenius theorem, but I cannot do that directly since $A$ is not necessarily a non-negative matrix. So I had the ...
Fernando's user avatar
0 votes
0 answers
43 views

Sparse NMF multiplicative update rules with zero-rows in coefficient matrix

I am working with Nonnegative Matrix Factorization, where I factor a nonnegative matrix $\mathbf{X}$ into a basis matrix, $\mathbf{W}$ and a coefficient matrix, $\mathbf{H}$. $$\mathbf{X}\approx \...
madsnibe's user avatar
0 votes
0 answers
10 views

What can I say about the column space of the product of two nonnegative softmax matrices?

Let $\mathcal S(\cdot)$ denote applying softmax transform along the first dimension. Given a nonnegative matrix $\mathcal S(\mathbf A \mathbf C^\top) \in \mathbb R_+^{m \times n}$ with variable ...
Kaiwen's user avatar
  • 33
0 votes
1 answer
114 views

Product of copies of a matrix and its transpose.

Let $M$ be a square (entrywise) nonnegative matrix, and suppose that $M^n$ is (entrywise) positive for some $n\in\mathbb{N}$. Consider now a product of $n$ matrices such that each of the matrices ...
GaussJordan's user avatar
0 votes
0 answers
10 views

Strange behaviour of Symmetric NMF with L1-norm distance

I am trying to validate a symmetric NMF model based on the L1-norm distance, that is $$min_{U\geq0} \|X - UU^T\|_1$$ However, after implementing it, I got very strange results. The model works very ...
MathLearner's user avatar
3 votes
0 answers
66 views

Spectral Radius of the Convex Combination of Identity Matrix and a Nonnegative Matrix

Let $D = \operatorname{diag}(d_1, d_2, \ldots, d_n)$ with each of its diagnal entry $d_i \in (0,1)$. $B$ is a non-negative matrix. Consider the following matrix $$ A = DI + (I-D)B, $$ where $I$ is ...
maphado fan's user avatar
1 vote
2 answers
71 views

Positive / negative (and so on) definite matrix. Confusion about the terms

I have problems in understanding the terminology used in Sylvester's Criterion about the "sign" of a matrix. I got the "positive-definite", the "negative-definite", the &...
Heidegger's user avatar
  • 3,492
2 votes
1 answer
53 views

Efficiently Finding a Rotation that Makes a Set of Vectors with Arbitrary Entries Non-Negative

Given a set of $k$ vectors ${x_1, x_2, ..., x_k} \in \mathbb{R}^n$ with arbitrary entries, we seek an efficient algorithm to compute an orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ that can ...
The One's user avatar
  • 834
5 votes
3 answers
140 views

Intuition of $D\leftarrow XC^{T}\text{diag}(C1_n)^{-1}$ update rule in matrix factorization

I am reading this paper where they use Matrix Factorization over Attention mechanism in their Hamburger model. In section 2.2.2 they say, Vector Quantization (VQ) (Gray & Neuhoff, 1998), a ...
WhyMeasureTheory's user avatar
2 votes
1 answer
73 views

Rewriting $||x-y|-z|$, for non-negative $x$, $y$, $z$, in a way that does not involve nested absolutes

Is there an idea that resolves nested value expressions into several separate expressions each using a single absolute value? Something similar like resolving the max function using the absolute value....
chickenNinja123's user avatar
2 votes
2 answers
139 views

Can the kernel of a quasi-positive matrix contain a positive vector?

Let $A$ a $n\times n$ quasi-positive matrix, i.e. $A$ has all non-negative entries $\ge 0$ and exists $n > 0$ such that $A^n$ is positive. We further assume that it has a $0$ eigenvalue, whose ...
user807606's user avatar
1 vote
1 answer
86 views

Spectral Radius of Perturbed Matrix

Let $A$ be an n-dimensional square matrix such that each entry of $A$ lies in $[0,1]$, i.e., $a_{ij} \in [0,1]$ for all $1\le i,j\le n$. Let $\widetilde{A}$ be a perturbed version of $A$ where some ...
GA-Student's user avatar
1 vote
1 answer
139 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
4 votes
0 answers
134 views

Dimension of the fixed space of stochastic matrices (reference request)

Let $A \in \mathbb{R}^{d \times d}$ be row stochastic (i.e., all entries of $A$ are $\ge 0$, and each row sums up to $1$. Let $G(A)$ denote the directed graph that is associated to $A$, i.e., $G(A)$ ...
Jochen Glueck's user avatar
3 votes
0 answers
33 views

Can we determine whether a symmetric matrix appended by one column/row maintains the Perron-Frobenius property?

Assume we are given a symmetric,non-negative, irreducible matrix $A \in \mathbb{R}^{n \times n}$. Then by the Perron-Frobenius theorem, there exists an eigenvector $v \in \mathbb{R}^n$ for the ...
a_student's user avatar
  • 1,504
0 votes
0 answers
31 views

Are bands of function spaces what I think they are?

Consider some compact set $K$ and the space of continuos functions $C(K,\mathbb{R})$. We obviously can define an algebra on this space by defining multiplication as $fg(i) = f(i) g(i)$ A band $B$ is ...
a_student's user avatar
  • 1,504
2 votes
0 answers
93 views

Krein-Rutman theorem for kernel operators

For a matrix $A \in \mathbb{R}^{n \times n}$, we have the well-known Perron-Frobenius-Theorem which among other things establishes the following properties: If $A$ is positive (i.e. $A_{ij}>0 \ \...
a_student's user avatar
  • 1,504
0 votes
1 answer
433 views

Perron-Frobenius theorem for reducible non-negative matrices

Let $M$ be a non-negative matrix ($M_{ij}\geq 0$ for all $i,j$). If $M$ is irreducible, then we know that there exists an eigenvalue $\lambda$ of $M$ that equals the spectral radius $\rho(M)$ and has ...
Marlo's user avatar
  • 1,213
2 votes
0 answers
48 views

What characterizes the set of matrices that admit non-negative eigenvectors (w. positive eigenvalue)?

Let us define the sets $$S = \{ M \in \mathbb{R}^{n \times n} | \exists \lambda, v \in \mathbb{R}_{\geq 0}^n : Mv = \lambda v\}$$ $$P = \{ M \in \mathbb{R}^{n \times n} | \exists \lambda \in \mathbb{R}...
a_student's user avatar
  • 1,504
1 vote
0 answers
378 views

How to understand the KL-divergence between two non-negative matrices

I am reading Non-negative Matrix algorithm using KL-divergence as metric. The KL-divergence is known as $D(P,Q)=\sum_i P(i)log\frac{P(i)}{Q(i)}$ for discrete distribution. However, the KL-divergence ...
Kelvin_neverKnow's user avatar
0 votes
0 answers
20 views

Does this function preserve the order of the nonnegative matrices

Suppose A and B are nonnegative matrices, that is, $A\geq 0$ and $B\geq 0$. Moreover, suppose $\|A\|_{\infty}<1, \|B\|_{\infty}<1$ and $A\leq B$. For $f(x)=x(2-x)$, we know that $f(x)$ is ...
Rebecca90's user avatar
0 votes
0 answers
21 views

How to perform NMF (Negative Matrix Factorisation) on the particular small matrix?

I read in the literature that SVD and NMF are somehow similar. Withou the probelm I am able to manually perform SVD on the matrix $$Z= \begin{bmatrix} 1 & -1 \\ 0 & -1 \\ 1 & 0 \end{...
user13696679's user avatar
1 vote
0 answers
44 views

Minimum of an inequality-constrained quadratic program

Let $A$ be an $n \times n$ strictly positive definite matrix with strictly positive entries. Let $c \in \mathbb{R}^n$ be an arbitrary vector. $$\begin{array}{ll} \underset{x \in \mathbb{R}^n}{\text{...
Student's user avatar
  • 41
0 votes
1 answer
132 views

How to prove the irreducible non-negative matrix has positive geometric sum?

Here is a question: A matrix $A=(A_{ij})_{n\times n}$ is called irreducible iff for every pairs $(i,j)$ we have $(A^k)_{ij}>0$ for some $1\leq k\leq n-1$. How to prove that matrix $A$ is ...
Faber Sung's user avatar
2 votes
0 answers
71 views

A matrix $A$ is $K$-irreducible if and only if no eigenvector lies on $\partial K$.

I'm studying the properties of nonnegative matrices, and I encountered a theorem for which I can not understand its proof. The theorem can be found in "Nonnegative matrices in the Mathematical ...
JustANoob's user avatar
  • 1,669
1 vote
0 answers
140 views

Criterion for non-negative matrix to have strictly real eigenvalues

Question: I am wondering whether there exists a sufficient and necessary condition that has to be obeyed by a non-negative $n\times n$ matrix $A=\{a_{ij}\}\in \mathbb{R}^{n \times n}$, which ...
Tomáš Bzdušek's user avatar
1 vote
1 answer
95 views

Rational left eigenvector in Perron-Frobenius theorem with nonnegative integer matrix

On pages 1133-1135 of Joel Friedman's On the road coloring problem, (PAMS 1990), we have an $n \times n$ primitive integer matrix $A$ with all row sums equal to $d \geq 2$. Clearly the right Perron ...
Sophie M's user avatar
  • 898
1 vote
0 answers
28 views

References on nonnegative matrices

I just started researching on non-negative matrices and their properties. Any suggestions on papers or sources for the theory and applications (ideally recent ones) of such matrices? I am currently ...
JustANoob's user avatar
  • 1,669
1 vote
0 answers
13 views

How to manually find NMF for a given matrix (of small size)

I would like to know (if possible) how does one find exact the non-negative matrix factorization ($AW$) of a given matrix $M$ of a small size? I know the problem is NP-hard. The method I know is by ...
user206904's user avatar
1 vote
1 answer
75 views

non negative matrices and spectrum

Let $r$ be the Perron Frobenius eigenvalue of a non negative matrix $A$. It seems that it's true that if $r, -r \in Spec(A)$ then $-A = S\cdot A \cdot S^{-1}$ with $S$ a diagonal matrix with $\pm 1$ , ...
Gianfranco's user avatar
1 vote
2 answers
474 views

Index of imprimitivity = Period of a matrix?

I am learning about the theory of non-negative matrices and trying to connect and reconcile various definitions I came across. The index of imprimitivity of an irreducible non-negative matrix $\...
paperskilltrees's user avatar
1 vote
0 answers
32 views

Help proving inequality involving (PF) eigenvalues/vectors

I am studying nonnegative matrices and their use in modelling Markov chains. I am curious about the nature of the sequence of partial sums of a spectral decomposition for an irreducible nonnegative ...
Jacob A's user avatar
  • 579
6 votes
1 answer
226 views

Proofs of Karpelevich's results about eigenvalues of nonnegative matrices.

Are there any books or papers written in English that contain proofs of the results obtained in the following paper? F.I. Karpelevich, On the characteristic roots of matrices with nonnegative ...
user1551's user avatar
  • 141k
1 vote
2 answers
96 views

Perron root of convex combination of nonnegative matrices

Given (irreducible) nonnegative matrices $A_i$ and a convex weighting $\hat{w}$ (i.e. a nonnegative set of reals ${w}$ s.t. $\sum_i w_i$) what can we deduce about the Perron root of $\sum_i w_i A_i$, ...
Jacob A's user avatar
  • 579
2 votes
1 answer
804 views

Perron-Frobenius Theorem poof by Brouwer fixed point

Could you suggest me a book where I can find a proof of Perron-Frobenius theorem (especially for nonnegative matrices) based on a Brouwer fixed point theorem?
Gabriela Bałazy's user avatar
1 vote
0 answers
49 views

Complex Eigenvalues of a Certain Matrix

Suppose that M is an $n\times n$ upper triangular matrix, with 1's on the diagonal, for which $-1\leq m_{ij}\leq 0$ for all $i<j$. Let N be the matrix $M^{-1}M^T$. Prove that the complex ...
George Maxwell's user avatar
1 vote
0 answers
190 views

Generate random nonnegative matrix with given condition number

I'm trying to generate random, real, elementwise nonnegative matrices with a given condition number $\kappa$. Dropping the nonnegativity condition I know that this can be done by generating a random ...
jackphen's user avatar
  • 127
0 votes
1 answer
275 views

How to prove that the linear rank of a matrix $\le$ its nonnegative rank? [closed]

I am studying nonnegative matrix factorization and came across this proposition in some lecture notes. In this context the nonnegative rank of a matrix $A$ is, I believe, the smallest number $r$ such ...
william_grisaitis's user avatar
2 votes
0 answers
114 views

Calculate perturbed eigenvector components of sub-stochastic (PF) matrix

I have a (column) sub-stochastic matrix, $P$, which is nonnegative and irreducible (hence satisfies the criteria of the Perron Frobenius theorem). I know its dominant eigenvalue, $\rho$ and left and ...
Jacob A's user avatar
  • 579
1 vote
1 answer
56 views

$3\times 3$ nonnegative matrices with purely imaginary eigenvalues

This question arised from the more generic "does there exist entrywise nonnegative matrices with some non-zero purely immaginary eigenvalues?" The answer is no for $2\times 2$ matrices (one ...
Exodd's user avatar
  • 11.4k
0 votes
1 answer
48 views

Exterior power of totally nonnegative square matrices

An $n$-by-$n$ square matrix $M$ is totally non-negative (TNN) if all its minors are non-negative. If we regard $M$ as the matrix for some linear operator $\varphi:V\rightarrow V$ under some basis $\{...
J. Wang's user avatar
  • 470
1 vote
1 answer
204 views

If A and B are Hermitian Matrices, $\text{tr}(ABAB) \geq 0$.

Can anybody help me with this problem. If $A$ and $B$ are Hermitian Matrices, then $\text{tr}(ABAB) \geq 0$. It is easy to show that the trace is a real number, but I cannot prove that it must be non-...
Hamed's user avatar
  • 51
0 votes
1 answer
130 views

Why doesn't the inverse of this matrix always exist?

Take $A$ square, non-negative, irreducible matrix, with Perron root $\rho(A)$. Let $Q = \rho(A)I - A$. Then it is argued (e.g. in the Handbook of Linear Algebra, Chapter 9) that the group inverse of $...
ippiki-ookami's user avatar
0 votes
0 answers
180 views

How to prove that for any matrix $A$, $A^{T}A$ and $AA^T$ are non negative?

I know that for any $A$, $AA^{T}$ and $A^{T}A$ are symmetric, so it's possible that these products are non-negative, where non negativity means that for a matrix $B$ to be non-negative, it has to ...
Indr's user avatar
  • 9
0 votes
0 answers
44 views

A non-negative matrix $A$ has an inverse if and only if $A>0$?

I know that $\mid A\mid$ cannot be zero. If $A$ is non-negative, then $x^{T}Ax\geq 0$. $A$ being positive is equivalent to having all its corners as positive. The largest corner $A$ can have is $A$ ...
minimalbob's user avatar
0 votes
0 answers
80 views

Proof of Perron Frobenius Theorem [duplicate]

I found this proof of Perron Frobenius Theorem using Banach Fixed Point Theorem very elegant. However, I can't quite get the claim (in the 6th line from the top on page 2) saying that $(A|w|)$ is a ...
user559678's user avatar
1 vote
1 answer
71 views

Does there exist a singular $3\times3$ stochastic matrix $A$ such that $a_{ii}>\max(a_{ij},a_{ji})$ for all $i\ne j$?

Yesterday, someone asked whether an $n\times n$ row-stochastic matrix $A$ that satisfies $a_{ii}>\max(a_{ij},a_{ji})$ for all $i\ne j$ is necessarily nonsingular. The answer is clearly positive ...
user1551's user avatar
  • 141k