Questions tagged [nonnegative-matrices]
A non-negative matrix is one whose entries are non-negative.
85
questions
1
vote
2
answers
42
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 &...
- 2,408
2
votes
1
answer
46
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 ...
- 782
5
votes
3
answers
133
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 ...
- 853
2
votes
1
answer
53
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....
- 581
2
votes
2
answers
130
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 ...
- 411
1
vote
1
answer
51
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 ...
- 159
1
vote
1
answer
62
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
3
votes
0
answers
107
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)$ ...
- 752
3
votes
0
answers
31
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 ...
- 1,394
0
votes
0
answers
30
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 ...
- 1,394
2
votes
0
answers
70
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 \ \...
- 1,394
0
votes
1
answer
234
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 ...
- 1,163
2
votes
0
answers
46
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}...
- 1,394
0
votes
0
answers
91
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 ...
0
votes
0
answers
18
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 ...
0
votes
0
answers
19
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{...
- 57
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{...
- 41
0
votes
1
answer
89
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 ...
- 11
2
votes
0
answers
61
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 ...
- 1,616
1
vote
0
answers
69
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 ...
- 546
1
vote
1
answer
88
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 ...
- 878
1
vote
0
answers
27
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 ...
- 1,616
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 ...
- 151
1
vote
1
answer
66
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$ , ...
- 51
1
vote
2
answers
369
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 $\...
- 609
1
vote
0
answers
31
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 ...
- 577
5
votes
1
answer
185
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 ...
- 134k
1
vote
2
answers
84
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$, ...
- 577
2
votes
1
answer
554
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?
1
vote
0
answers
47
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 ...
1
vote
0
answers
139
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 ...
- 83
0
votes
1
answer
183
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 ...
2
votes
0
answers
90
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 ...
- 577
1
vote
1
answer
51
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 ...
- 10.6k
0
votes
1
answer
41
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 $\{...
- 470
1
vote
1
answer
155
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-...
- 51
0
votes
1
answer
120
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 $...
- 1,072
0
votes
0
answers
101
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 ...
- 9
0
votes
0
answers
42
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$ ...
0
votes
0
answers
78
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 ...
- 51
1
vote
1
answer
67
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 ...
- 134k
1
vote
0
answers
154
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 ...
- 83
1
vote
1
answer
79
views
Determinant for the element-wise derivative of a matrix
Let $M$ a $d\times d$ matrix with entries $$M_{ij}=x^{\alpha_j+i-j},$$ with $\alpha_j$ a non-negative integer. It is possible to write an expression for $det\left(\frac{d^{k}}{dx^k}M\right)$ in terms ...
3
votes
0
answers
44
views
Rank of non-negative matrices
Are there some easy ways to verify conditions on a nonnegative matrix with $0$ diagonal which ensure that it is conditionally negative definite (i.e., $x^TAx \le 0$ for all $x$ with $x^T\mathbf{1}=0$ ...
0
votes
1
answer
340
views
Definiteness of Negative Symmetric Matrix with Largest Values on the Diagonal.
I have a symmetrix matrix, $M = M^T$ which has negative values everywhere i.e., $M_{i,j}<0$ for all $i, j$. Furthermore, I know that we have $M_{i, i} \leq M_{i, j} \forall i,j$ and additionally ...
- 123
0
votes
1
answer
133
views
How to prove a number is in the A002620 sequence.
I am working on a project in PHP where I generate a number and want to see if said number is part of the A002620 sequence. I've started by looking at https://oeis.org/A002620 "Quarter-squares: floor(n/...
- 101
1
vote
1
answer
227
views
Spectrum of irreducible matrix
The Wikipedia article on the Perron-Frobenius theorem claims that (without referencing a proper proof):
The key feature of theory in the non-negative case is to find some special subclass of non-...
1
vote
1
answer
33
views
Calculation of a limit, using left eigenvectors, an eigenvector and a positive matrix
I've tried to calculate the limit of 1 over the Spectral Radius of a positive Matrix A times the Matrix A itself, the whole thing to the power of k, but it went wrong somewhere. My attempt is in the ...
- 11
0
votes
2
answers
51
views
Nonnengative matrices sum and produt
I can proof this situation on this way?
If $A$ and $В$ are irreducible, then $AB$ is irreducible.
Proof:
hyphothese: $A\geq0, B\geq 0$ are irredicible
Thesis: $AB$ is irreducible.
If $A\geq0$ is ...
0
votes
1
answer
234
views
Irreducible nonnegative matrices
I would like to aply this theorem in a pratic an exercise, the theorem i:
A nonnegative square matrix $A=\left(a_{ij}\right)$ is irreducible if and only
if for each $(i, j)$ there exists an integer $...