Questions tagged [nonnegative-matrices]
The nonnegative-matrices tag has no usage guidance.
85
questions
6
votes
2
answers
1k
views
Extreme points of transportation polytope
I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the transportation polytope. What are the extreme points of ...
- 37.2k
2
votes
1
answer
157
views
Non-negative integer matrix representation of a fusion ring
Context: I am a physics grad student working on topological lines in 2D CFTs.
Let $A$ be a unital based $\mathbb{Z}_{+}$ ring with finite rank (or a Fusion ring) with the basis $B = \{b_1, b_2, \dotsc ...
CommunityBot
- 1
0
votes
2
answers
57
views
Nondegeneracy of dominant singular value and positivity of dominant singular vector of connected nonnegative matrix
Call a (not necessarily square) nonnegative matrix $M$ connected if there do not exist permutation matrices $P$ and $Q$ such that $PMQ=\begin{pmatrix}A&0\\0&B\end{pmatrix}$ for some $A$ and $B$...
- 674
1
vote
0
answers
56
views
Eigenvalues of a subset of matrix semigroup
My apologies for slightly longer post but I wanted to explain lower dimensional cases and their proofs before asking the actual question, which starts after the phrase The general case below.
A two-...
- 2,758
26
votes
2
answers
1k
views
Uniquely reconstruct a matrix $M$ from its inverse $M^{-1}$ if $n$ elements of $M^{-1}$ are unknown and $n$ elements of $M$ are given
This question was motivated by a recent MO post. You know $n$ elements of the $N\times N$ matrix $M$ and you do not know $n$ elements of the inverse $M^{-1}$ (but you know the other $N^2-n$ elements ...
- 51.6k
7
votes
2
answers
740
views
An extension of the Golden-Thompson inequality
For three symmetric positive semidefinite matrices $A, B,C$, I am trying to figure out if the following inequality holds, at least in some cases:
$$ \operatorname{tr} \left( A e^{B+C} \right) \leq \...
2
votes
1
answer
7k
views
Properties of eigenvalues of general nonnegative matrices
I am aware, that an answer to this question can be found via Perron-Frobenius theory or something very similar, but unfortunately I am far from being an expert in the field and I am unable to find the ...
7
votes
1
answer
439
views
"Unimodality" of the positive eigenvector of a non-negative irreducible matrix?
Consider an eigenvalue / eigenvector problem for a matrix $A$ that is known to be non-negative and irreducible (so the Perron-Frobenius theorem applies):
$$\sum_j A_{ij} x_j = \lambda x_i$$
Here $\...
- 864
1
vote
1
answer
219
views
Growth rates of ‘sub-traces’ of matrices
Consider an aperiodic, non-negative and non-zero $m\times m$ matrix $A$. Here aperiodic means that there exists an integer $n$ such that every entry of $A^n$ is strictly positive. By the Perron–...
1
vote
1
answer
159
views
Second order matrix differential equation in the space of symmetric positive definite matrices
In the construction of interpolations in the space of Gaussian measures, I encountered a second order matrix differential equation in the set of symmetric positive definite matrices $\mathbb{S}_+^d\...
- 118k
8
votes
2
answers
660
views
Finding a matrix from its diagonal and the off-diagonal elements of its inverse?
This question comes from https://stats.stackexchange.com/questions/457375/recover-full-covariance-matrix-from-covariance-diagonal-and-precision-off-diagon where it have not found answers. So, let $\...
- 151k
47
votes
3
answers
4k
views
Is this proof of Perron's theorem correct, and if so is it original?
A few years ago, I came up with this proof of Perron's theorem for a class presentation:
https://pi.math.cornell.edu/~web6720/Perron-Frobenius_Hannah%20Cairns.pdf
I've written an outline of it below ...
- 4,958
1
vote
0
answers
76
views
Weird transportation polytope
I'm looking to compute extremal points of a weird polytope. This polytope contains all matrices with positive entries $A \in \mathcal M_{n,m}\left(\mathbb R_+\right)$ such that:
every row sum except ...
- 686
4
votes
1
answer
296
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 1,432
1
vote
0
answers
83
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.7k
8
votes
0
answers
394
views
Eigenvalues of cyclic stochastic matrices
Let's consider the following $n \times n$ cyclic stochastic matrix
$$ M= \begin{pmatrix}
0 & a_2 & & & &b_n \\\
b_1 & 0& a_3& &&& \\\
& b_2 & ...
- 650
0
votes
1
answer
110
views
Matrix iteration for non-negative matrices. Does it converge to some eigenvector?
Let $A$ be a non-negative (entrywise) matrix such that $A(1,1)>0$. Set $u=(1,0,0,...,0)^T$. Is it always true that there exists a non-negative eigenvector $v$ of $A$ such that $\lim_{n\rightarrow\...
- 21
11
votes
2
answers
710
views
Encyclopedia of properties of nonnegative matrices
I'd like to buy a book that contains more or less all known properties of elementwise nonnegative nonnegative matrices, i.e. matrices $A$ such that $a_{ij} \ge 0$ for all $1 \le i,j \le n$.
Chapter 8 ...
- 1,711
5
votes
0
answers
426
views
Non-diagonalizable positive matrices
Let $n\geq 3$ and $E_n$ be the set of $n\times n$ matrices $A$ satisfying the $3$ following properties:
$\bullet$ its entries $(a_{i,j})$ are positive integers.
$\bullet$ the eigenvalues of $A$ are ...
- 3,574
22
votes
3
answers
2k
views
Sampling from the Birkhoff polytope
The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope
Recently someone asked me if I knew
How to sample (in polynomial time) ...
- 31.5k
4
votes
2
answers
401
views
Frobenius normal form of a doubly stochastic matrix
If $A \in M_n(\mathbb{C})$, then $A$ is called reducible if there is a permuation matrix $P$ such that
$$
P^\top A P =
\begin{bmatrix}
A_{11} & A_{12} \\
0 & A_{22}
\end{bmatrix}, $$
in ...
- 1,711
1
vote
0
answers
86
views
Solution of a manipulated equation vs the maximum eigenvalue and eigenvector of a non-negative matrix
Lets assume we have the following equation:
$AU=\lambda U \Rightarrow\left[
\begin{array}{c|c|c}
0 &A_{12}&A_{13}\\
\hline
A_{21}& 0& A_{23}\\
\hline
A_{31}&A_{32}&0
\end{...
- 21
5
votes
1
answer
413
views
Determining the primitive order of a binary matrix
Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows
$$
{\bf A}_n=\left(
\begin{array}{c}
0&0&\cdots&0&0&0&0&1&1\\
0&0&\cdots&0&0&...
1
vote
1
answer
481
views
Is there a way to turn a non convex set to a convex one? [closed]
Perhaps the question is rather vague, but if we are given a non-convex set S, can we construct some invertible mapping f so that f(x) becomes a convex set?
In my problem , I am given a set of matrix ...
- 19
25
votes
5
answers
2k
views
When is a matrix power nonnegative
The following question came up today during a discussion:
Suppose $A$ is an $n \times n$ real matrix. Is there some way to tell whether there exists an integer $q > 0$ such that $A^q$ is ...
- 1,711
7
votes
1
answer
383
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
CommunityBot
- 1
1
vote
0
answers
346
views
The problem about the eigenvalues of Metzler matrix in a special form
Let $G$ be a square matrix of the form
$$G=\left[ \begin{array}{cc}
A & B \\
C & 0 \\
\end{array}
\right]$$
with $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \...
3
votes
1
answer
985
views
The largest eigenvalue of a binary matrix with specific density
I would like to find the largest eigenvalue of an $n \times n$ binary matrix of density $p$, i.e., with $p n^{2}$ ones and $(1-p) n^{2}$ zeros. Any idea or reference is welcome.
- 4,709
8
votes
1
answer
287
views
Distance from nonnegativity of some orthonormal vectors
Suppose that $1 < k < n$. Does there exist a constant $\beta > 0$, such that for every $k$ orthonormal vectors $f_1,\ldots,f_k \in \mathbb R^n$,
there exist $k$ orthonormal vectors with ...
- 118k
5
votes
2
answers
274
views
An equality relation for complex numbers off the nonnegative real axis [closed]
For every complex number $z$ off the nonnegative real axis there exist positive numbers $p_0,... ,p_n$ such that $\sum_{i=0}^n p_iz^i = 0$.
Finding difficulty in proceeding with the problem. Need ...
- 4,669
5
votes
1
answer
597
views
Nonnegative matrices and singular values
I would like to prove (or prove it is not true with a counter example) the following result:
Let $A$, $B$ be two squares matrices of size $n\times n$ with positive entries.
If $A \leq B$, then $\sum_{...
- 11.6k
1
vote
0
answers
45
views
Rank Optimization over semi-definite constrains
Let $X$ and $Y$ be finite dimensional Hilbert spaces $\mathbb{C}^n$ and $\mathbb{C}^m$, $L(X)$ and $L(Y)$ be the sets of linear operators of $X$ and $Y$, $\text{Herm}(X)$ and $\text{Herm}(Y)$ be the ...
CommunityBot
- 1
6
votes
0
answers
99
views
What is this matrix decomposition called and does it exist always? - II
Given a rank $2r$ matrix $M\in\Bbb Q_{\geq0}^{n\times n}$ can we find two matrices $M_+\in\Bbb Q_{\geq0}^{n\times n}$ and $M_-\in\Bbb Q_{\geq0}^{n\times n}$ each of rank at most $r$ such that $M=M_+-...
- 13.7k
4
votes
1
answer
291
views
What is this matrix decomposition called and does it exist always?
Given a rank $2r$ matrix $M\in\Bbb Q^{n\times n}$ can we find two matrices $M_+\in\Bbb Q_{\geq0}^{n\times n}$ and $M_-\in\Bbb Q_{\geq0}^{n\times n}$ each of rank $r$ such that $M=M_+-M_-$ holds?
...
- 1,005
4
votes
0
answers
927
views
Generate non-negative linear combinations of non-negative vectors with different supports
(I will not be surprised if this problem has been solved and/or has a trivial solution – I just do not know the right terminology to google for it.)
So the problem is as follows. I have an $m \...
- 325
2
votes
0
answers
2k
views
Sufficient conditions for positive semidefiniteness of block matrix
$\newcommand{\Re}{\mathbb{R}}$I m looking for sufficient conditions that may guarantee positive semidefiniteness (PSD) of a block matrix
$$A = \begin{bmatrix} A_{1,1} & \cdots & A_{1,n} \\ \...
- 121
1
vote
1
answer
218
views
zero patterns of M-matrices and their invereses
Suppose that the matrix $M$ has non-positive off-diagonal elements. The matrix $M$ is
said to be an M-matrix if $M$ is non-singular and each entry of $C:=M^{−1}$
is non-negative.
I think I've proved ...
- 19.4k
4
votes
1
answer
405
views
Proving convergence of modified ALS for non-negative matrix factorization
The general Non-Negative Matrix Factorization (NMF) problem asks that for given a matrix $X \in \mathbb R^{m,n}_{0+}$ (with this notation meaning a matrix containing real numbers greater than or equal ...
- 28.4k
4
votes
1
answer
214
views
Spectrum of primitive nonnegative integer matrices
Let $P(X) = a_nX^n + \cdots + a_1X + a_0$ with $a_i \in \mathbb Z$.
Question 1. Is there an efficient criterion on the $a_i$ to decide if there exists a primitive nonnegative integer matrix with ...
CommunityBot
- 1
5
votes
4
answers
772
views
Expected value of the spectral radius of a random nonnegative matrix
I have two questions, the second of which is related to this question posed by Denis Serre.
Let $X$ be a random variable and suppose that $Y=|X|$ (e.g., $Y$ could be the folded normal distribution). ...
- 7,434
1
vote
0
answers
266
views
Interlacing Suleĭmanova spectra
A set of real numbers $\{\lambda_1, \dots, \lambda_n \}$, $n \geq 1$, is called a Suleĭmanova spectrum if it contains exactly one positive value and $\sum_{i=1}^n \lambda_i \geq 0$. (It is well-known ...
- 1,711
2
votes
1
answer
183
views
Perturbation of linear system of equations: Is the solution still non-negative?
Let $A = (a_{ij})_{i,j=1,\dots,n}$ be a matrix such that
$a_{ij} \ge 0$ for all $i,j = 1, \dots, n,$ and
$A$ is positive definite.
Let $I$ be the identity matrix, and $\pmb{1}$ the vector ...
CommunityBot
- 1
12
votes
3
answers
699
views
How to find Suleimanova's work on the Nonnegative Inverse Eigenvalue Problem?
Many papers cite the work of Suleimanova when studying inverse eigenvalue problems - in particular, the nonnegative inverse eigenvalue problem (NIEP). However, I cannot seem to find her work anywhere....
- 1,711
5
votes
2
answers
1k
views
spectral radius monotonicity
I encountered an inequality when reading a paper. Can someone help to show how to prove it?
Let be the spectral radius of matrix $A$ or $\rho(A)=\max\{|\lambda|, \lambda \text{ are eigenvalues of ...
3
votes
1
answer
789
views
A spectral radius inequality
Define $\rho(A)$ to be the spectral radius of a square matrix $A$. Let $S$ and $T$ be two non-negative square matrices and $h$ a real number such that $\rho(S+T) < h$. Show that $\rho((hI-S)^{-1}T) ...
3
votes
2
answers
517
views
Number of $\{0,1\}$ matrices with distinct rows and distinct columns
How many $M\in\{0,1\}^{r\times c}$ are there such that each row and each column of $M$ is distinct?
How many classes of matrices in $\{0,1\}^{r\times c}$ up to permutation equivalence are there such ...
CommunityBot
- 1
2
votes
1
answer
206
views
Perron-Frobenius for a "maximum" of matrices
Consider a set of positive matrices $(P_k)_{k\in K}$ in $\mathbb R^{p\times p}_{++}$ ($P_k$ is positive in the sense that all entries of $P_k$ are positive).
Let $X_0\in\mathbb R_{++}^p$ and define ...
- 1,167
4
votes
2
answers
185
views
Requesting reference for result from linear algebra on Schur complements of M-matrices
In my research in linear algebra, I have come across a useful result stating that the Schur complement of a principal non-singular submatrix of an M-matrix is also an M-matrix, but I have never found ...
- 28.4k
4
votes
1
answer
541
views
No arbitrary product of matrices has eigenvalue 1?
Consider the matrix $D$, adjacency matrix of an undirected graph $G$ on $n$ vertices, with the notation that $d_{i,i}=0,\forall i$.
The matrices $A_i$ are constructed from Identity matrices, $I_{n*n}$...
- 143
1
vote
1
answer
197
views
nonnegative solution of nonhomogeneous under-determined linear system of equations
For a set of under-determined linear equations, I was wondering if there is any closed form for all non-negative solutions? Is there a way to analytically characterize the feasibility set of such ...
- 13.7k