Questions tagged [nonnegative-matrices]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
34 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$ , ...
1
vote
2answers
98 views
+50

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 $\...
0
votes
0answers
4 views

References for Random Matrix Theory applied to NMF problems

Nonnegative Matrix Factorization (NMF), is defined as follows: Consider a matrix $X\in\mathbb{R}^{m\times n}_{\geq 0}$. Then, we look for approximation, \begin{align*} \hat{X}\approx UV^T, \end{align*}...
1
vote
0answers
20 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 ...
0
votes
0answers
18 views

Need help with this Bayesian hierarchical model

Let consider the following factorization problem \begin{align} X \simeq & WH, \\ & X \in \mathbb{R}^{M \times N}, W \in \mathbb{R}^{M \times K}, H \in \mathbb{R}^{K \times N}, \end{align} with ...
2
votes
1answer
59 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 ...
0
votes
0answers
17 views

Lower bound for the difference of matrix spectral radii

Let $A$ and $B$ be two nonnegative, symmetric, irreducible matrices with the spectral radii $r(A)$ and $r(B)$, respectively. Show that $r(A)-r(B) \ge x^t (A-B)x$. I am really stuck at this point. I ...
1
vote
2answers
52 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$, ...
1
vote
1answer
77 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
0answers
32 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 ...
0
votes
0answers
45 views

Show that $\rho(A) \geq \gamma^{1/n}$ if $\gamma := a_{1\sigma(1)}a_{2\sigma(2)} \cdots a_{n\sigma(n)}$ and $\sigma$ is the permutation from 1 to $n$.

Hi I am stuck to work on this problem. Can somebody help me at least give me the hint. I would appreciate it. Thanks in advance Let $A = [a_{ij}] \in M_n$ be nonnegative, let $\sigma$ be a given ...
1
vote
0answers
22 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 ...
0
votes
1answer
28 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
0answers
43 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 ...
0
votes
0answers
9 views

Convergence of non-linear vector fixed point iteration

Let $A$ be an $d\times d$, non-negative, symmetric matrix. Let $\mathbf{a}\in\mathbb{R}^d$ be a positive vector and $\mathbf{x}_0 = [1,1,\cdots,1]^T$. Under what conditions on $A$ and $\mathbf{a}$, ...
1
vote
1answer
36 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 ...
0
votes
1answer
29 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 $\{...
0
votes
0answers
22 views

Does the nuclear norm define a kernel?

Consider a function $k : \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n} \to \mathbb{R}_+$, defined by $k(X, Y) =\Vert X^T Y \Vert_*$ where $\Vert \cdot \Vert_*$ denotes the nuclear norm (sum ...
1
vote
1answer
70 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-...
0
votes
1answer
63 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 $...
0
votes
0answers
45 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 ...
0
votes
0answers
35 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
0answers
11 views

On $C_{12}$ in $|||A|||_1 \leq C_{12}|||A|||_2$ when $A \in \mathbb{R}^{n\times n}_+$

I know from Horn and Johnson's matrix analysis that for a matrix $A \in \mathbb{R}^{n\times n}$ the best possible constant $C_{12}$ in \begin{equation*} |||A|||_1 \leq C_{12}|||A|||_2 \end{equation*} ...
0
votes
0answers
71 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 ...
1
vote
1answer
46 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 ...
1
vote
0answers
80 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
1answer
44 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
0answers
32 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
1answer
90 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 ...
0
votes
1answer
86 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/...
1
vote
1answer
67 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
1answer
24 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 ...
0
votes
2answers
45 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
1answer
39 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 $...
1
vote
0answers
41 views

Invertible matrix with nonnegative entries [duplicate]

Let $A \in \text{GL}(n,\mathbb R)$ with all nonnegative entries such that $A^{-1}$ also has all nonnegative entries. How many nonzero entries does $A$ have, what are their locations, and what are the ...
0
votes
1answer
47 views

Special non-negative matrix decomposition

Assume we have the following decomposition: $M=AWA^T$ Where: $M$ is non-negative symmetric (i.e. $M_{i,j}\ge{0}$ and $M_{i,j}=M_{j,i}$) $A$ is right stochastic (entries are non-negative and rows ...
1
vote
1answer
64 views

Please help me prove a positive definite matrix!

Prove that: If $W$ is a diagonal matrix having positive diagonal elements and size $(2^n–1)\text{x}(2^n – 1)$, $K$ is a matrix with size $(2^n – 1)\text{x}n$, then: $A = K^T[W^{-1} - K(K^TWK)^{-1}K^T]...
1
vote
1answer
91 views

prove negative definiteness of $\mathbf{1}_{(0, \infty)}(x)$

I would like to show the negative definiteness of $\mathbf{1}_{(0, \infty)}(x)$ with certain condition. Let $h\left(x_{i}, x_{j}\right)=\mathbf{1}_{(0, \infty)}\left(|x_{i}-x_{j}|\right)$. if $c_{1}...
0
votes
1answer
49 views

In non-negative matrix factorization, what is the difference between row clustering and column clustering in the following context?

In Orthogonal Nonnegative Matrix Tri-factorizations for Clustering, $min||X-FG^T||^2_{F}$, s.t. $F^TF=I,G^TG=I, F>=0, G>=0$. $X\in\mathbb{R}^{d\times n}$, $F\in\mathbb{R}^{d\times k}$, $G\in\...
0
votes
1answer
70 views

Non negative irreducible matrix times a positive matrix

Let $A$ be a real non negative irreducible matrix, meaning that $(a_{ij})\geq 0$ I know from a theorem in Minc's book that $(I+A)^{n-1}>0$. It is also stated in the book that $B=(I+A)^{n-1}.A>...
1
vote
0answers
33 views

Prove $(E+A)^{n-1}$ is a nonnegative matrix with positive elements

Suppose $A$ is an $n\times n$ irreducible nonnegative matrix, prove that $(E+A)^{n-1}$ is a nonnegative matrix with positive elements. I think that this excise can be proved by definition. So I tried ...
0
votes
1answer
491 views

What are the features extracted in non-negative matrix factorization?

The application of NMF is related to extracting features in original data present as a matrix. An important problem when utilizing NMF for feature extraction is the choice of rank r. However I can't ...
0
votes
0answers
303 views

Non-Negative Vs Positive Semi Definite

A matrix is PSD if $$\langle Ax, x\rangle \ge 0, \forall x \in H$$ Where, H is a hilbert space and A is a mapping $H \rightarrow H$. Is it the same as being Non-negative? I couldn't seem to find a ...
0
votes
2answers
324 views

Prove the inverse of a nonnegative matrix is nonnegative

Defintion of a nonnegative matrix: Symmetrical matrix $A: n \times n$ is non-negatively defined when $A > 0$ or $A ≥ 0$ We have to prove the following: If $A$ is defined as a nonnegative matrix, ...
1
vote
0answers
41 views

Proving that a matrix is nonnegative if its powers are nonnegative

I am working on a problem involving doubly stochastic matrices where I must prove that $P$ is doubly stochastic if and only if $P^k$ is doubly stochastic for $k = 1, 2, ...$ It is easy to show that if ...
0
votes
0answers
63 views

If $A$ is nonnegative definite then so is $BAB'$

Let $A$ be an $m$x$m$ nonnegative definite matrix, while $B$ is an $n$x$m$ matrix. Show that $BAB'$ is a nonnegative definite matrix. I know by definition that a nonnegative definite matrix has the ...
2
votes
1answer
53 views

Number of weak components in powers of imprimitive digraphs

Given any strongly connected digraph $G$ and any $n\in\mathbb{N}$ if we let $d(G)$ be the greatest common factor of the lengths of all the directed cycles in $G$ then does the $n^{\text{th}}$ power ...
1
vote
1answer
258 views

Perron Frobenius Theorem modified

On this site I found a modified version of Perron Frobenius Theorem Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then: 1 is an eigenvalue of multiplicity one. 1 is ...
1
vote
0answers
34 views

Convergence of Matrix product (not memoryless)

I try to analyze the following iterative matrix product: $x_{i+1} = A_{i} \cdot x_{i}$. The matrices $A_i$ are defined as follows: $A_i = \begin{bmatrix} \frac{1}{2\sqrt{x_{i,1}^2 + y_{i,1}^2}} &...
2
votes
2answers
83 views

Positive matrices are diagonalizable in $\mathbb C$?

Let $A$ be a square matrix with real positive entries. Is it true that it is diagonalizable in $\mathbb C$? My guess is that it is false, but the counterexample can't be a $2\times 2$ matrix, since ...