Questions tagged [nonnegative-matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Memming's user avatar
  • 291
12 votes
2 answers
3k views

Eigenvalues of nonnegative integer matrices

Edit I realized that the key piece of information that I need is question 1, and so I'd like to rephrase this post: What are the possible eigenvalues of nonnegative integer matrices? Any answer to ...
Brian Rushton's user avatar
21 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) ...
Suvrit's user avatar
  • 28.4k
7 votes
1 answer
4k views

How much can a diagonal matrix change the eigenvalues of a symmetric matrix?

Suppose that we have a symmetric matrix ${\bf S}$ with eigenvalue decomposition ${\bf S} = {\bf Q}{\bf \Lambda}{\bf Q}^T$. Assume that we have two diagonal matrices ${\bf D}_1$ and ${\bf D}_2$ that ...
Anadim's user avatar
  • 449
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 ...
Carlo Beenakker's user avatar
8 votes
2 answers
651 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 $\...
kjetil b halvorsen's user avatar
6 votes
2 answers
437 views

Is a normal matrix satisfying $A^TA=...$ circulant?

Let $A=\{a_{ij}\}$ be a normal matrix such that $a_{ij}\geq 0$ with equality iff $i=j$. Suppose that $$ A^TA=\begin{pmatrix} a & b & \cdots & b\\ b & a & \ddots & \vdots\\ \...
pre-kidney's user avatar
  • 1,289
4 votes
1 answer
291 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\...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
289 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? ...
Turbo's user avatar
  • 13.7k
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 ...
042's user avatar
  • 83
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 ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
145 views

Are certain normal matrices circulant? (Part 2)

Let $\mathcal{F}$ denote the family of real normal matrices $A$ such that $ A^TA=\begin{pmatrix} a & b \\ b & \ddots \end{pmatrix}$, for $b>0$. As a user observed in the solution of Part 1 ...
pre-kidney's user avatar
  • 1,289