# On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory

Yeow Meng Chee, Quoc-Tung Le, Duy Hoang Ta

► To cite this version:

Yeow Meng Chee, Quoc-Tung Le, Duy Hoang Ta. On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory. 2024 IEEE International Symposium on Information Theory (ISIT 2024), Jul 2024, Athènes, Greece. pp.1955-1960, 10.1109/ISIT57864.2024.10619320. hal-05082382

HAL Id: hal-05082382

https://hal.science/hal-05082382v1

Submitted on 23 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory

Yeow Meng Chee*, Quoc-Tung Le†, and Hoang Ta*

*Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore

†Toulouse School of Economics, Université de Toulouse, France

**Abstract**—In this paper, we study the asymptotic nonnegative rank of matrices, which characterizes the asymptotic growth of the nonnegative rank of fixed nonnegative matrices under the Kronecker product. This quantity is important since it governs several notions in information theory such as the so-called exact Rényi common information and the amortized communication complexity. By using the theory of asymptotic spectra of V. Strassen (J. Reine Angew. Math. 1988), we define formally the asymptotic spectrum of nonnegative matrices and give a dual characterization of the asymptotic nonnegative rank. Complementary to the nonnegative rank, we introduce the notion of the subrank of a nonnegative matrix and show that it is exactly equal to the size of the maximum induced matching of the bipartite graph defined on the support of the matrix (therefore, independent of the value of entries). Finally, we show that two matrix parameters, namely rank and fractional cover number, belong to the asymptotic spectrum of nonnegative matrices.

## I. INTRODUCTION

The nonnegative rank of a nonnegative matrix $A$ of size $m \times n$, denoted by $R_+(A)$, is the smallest integer number $r$ such there exist two nonnegative matrices $B$ and $C$ of size $m \times r$ and $r \times n$ respectively such that $A = BC$ ($BC$ is the usual matrix product between $B$ and $C$). The notion of nonnegative rank can be found in various fields such as combinatorial optimization [1] and communication complexity [2], [3], [4], [5]. For instance, in two-party communication complexity, two players compute a boolean function $f: \mathcal{X} \times \mathcal{Y} \to \{0,1\}$ on inputs $(x,y) \in \mathcal{X} \times \mathcal{Y}$ where each party holds only one argument (either $x$ or $y$). In this setting, the communication complexity $D(f)$ of the function $f$ is the minimum number of bits that need exchanging to evaluate $f$. Results in [3], [4] show that the logarithm of the nonnegative rank of the associated matrix $M_f$ of size $|\mathcal{X}| \times |\mathcal{Y}|$ defined by $M_f(x,y) = f(x,y)$ is a lower bound for the communication complexity, i.e., $\log R_+(M_f) \le D(f)$. Another application of nonnegative rank is in combinatorial optimization. In [1], it is shown that the minimum number of linear inequalities representing a given polytope can be determined by the nonnegative rank of a particular matrix. This quantity plays an important role in solving linear programming because the complexity of interior-point methods depends on the number of linear inequalities. Finally, it is demonstrated in [6], [7] that the minimum amount of information exchanged by two parties in order to sample from the bivariate probability distribution $p(x,y) = A_{x,y}$ represented by a matrix $A$ (assuming $A$ is

normalized so that $\sum_{x,y} A_{x,y} = 1$) can be determined by the nonnegative rank of $A$.

The asymptotic nonnegative rank, which is defined as the asymptotic growth of the nonnegative rank of a matrix under Kronecker product (see Equation (1) for its mathematical definition), is equally important since it is also related to many quantities in information theory and communication complexity such as the exact Rényi common information [8] and the amortized communication complexity [9]. However, in comparison to the nonnegative rank, the asymptotic counterpart is not equally well-studied. For this reason, in this paper, we make several contributions to the study of asymptotic nonnegative rank: first, we give a dual characterization of this notion as well as additional results that relate to it via the theory of asymptotic spectra. Historically, this theory was developed by V. Strassen in [10] (see also the exposition in [11, Part I]) to understand the arithmetic complexity of matrix multiplication (see, e.g., [12]). More recently, the theory of asymptotic spectra has been applied to a range of other problems in combinatorics [13], quantum information [14], [15], circuit complexity [16] and other domains [17], [18], [19]. Two related notions to the nonnegative rank and the asymptotic nonnegative rank, the nonnegative subrank and its asymptotic version, are also introduced and studied.

### A. Notations and Definitions

We define some basic notions that will be used in the rest of this paper. Let $A \in \mathbb{R}_+^{m_A \times n_A}$, $B \in \mathbb{R}_+^{m_B \times n_B}$ be two nonnegative matrices, the direct sum $A \oplus B$ and Kronecker product $A \otimes B$ are defined respectively by:

$$A \oplus B := \begin{pmatrix} A & 0 \\ 0 & B \end{pmatrix} \in \mathbb{R}_+^{(m_A+m_B) \times (n_A+n_B)},$$

$$A \otimes B := \begin{pmatrix} A_{1,1}B & \dots & A_{1,n_A}B \\ \vdots & \ddots & \vdots \\ A_{m_A,1}B & \dots & A_{m_A,n_A}B \end{pmatrix} \in \mathbb{R}_+^{m_A m_B \times n_A n_B},$$

where $A_{i,j}$ is the value of $A$ at the index $(i,j)$.

For $n \in \mathbb{N}$, denote $I_n$ the identity matrix of size $n$ and $\text{GL}^+(n) := \{A \in \mathbb{R}_+^{n \times n} | A^{-1} \in \mathbb{R}_+^{n \times n}\}$ the subgroup of $\text{GL}(n)$ whose elements and their inverses are nonnegative matrices.

Given a set $S$ equipped with a binary operator $\cdot : S \times S$, we say $(S, \cdot)$ is a commutative monoid if:
(1) The operator $\cdot$ is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot c), \forall a, b, c \in S$.

(2) The operator $\cdot$ is commutative: $a \cdot b = b \cdot a, \forall a, b \in S$.

(3) There exists an identity element $0$: $a \cdot 0 = 0 \cdot a = a, \forall a \in S$.

For a nonnegative matrix $A$, $\text{supp}(A) := \{(i, j) : A_{i,j} > 0\}$ the support of $A$ is the set of indices whose coefficient in $A$ is strictly positive. In this work, $\text{supp}(A)$ has two interpretations: either a subset of the index set or a binary matrix of the same size as $A$ whose coefficients at $(i, j)$ are equal to 1 if $(i, j) \in \text{supp}(A)$ and 0 otherwise.

**Asymptotic nonnegative rank:** The nonnegative rank is sub-multiplicative under Kronecker product. Indeed, given two nonnegative matrices $A, B$, suppose that $A = UV^T$ and $B = XY^T$, where $U, V, X, Y$ are nonnegative matrices, then $A \otimes B = (U \otimes X)(V \otimes Y)^T$. Therefore $R_+(A \otimes B) \le R_+(A) R_+(B)$. In general, $R_+$ is not multiplicative since there exists $A \in \mathbb{R}_+^{4 \times 4}$ such that $R_+(A) = 4$ and $R_+(A \otimes A) = 15 \ne R_+(A)^2$ [20]. For more similar examples, we refer to [20], [21]). Therefore, the *asymptotic nonnegative rank* is interesting to consider. Mathematically, the asymptotic nonnegative rank of nonnegative matrices is defined as follows.

$$ \tilde{\mathbb{R}}_+(A) := \lim_{n \to \infty} R_+(A^{\otimes n})^{1/n}. \quad (1) $$

Since the sequence $R_+(A^{\otimes n})^{1/n}$ is sub-multiplicative, by Fekete's lemma [22], we can prove that $\tilde{R}_+(A)$ is well-defined and the limit can be replaced by the infimum over $n$. Namely,

$$ \tilde{\mathbb{R}}_+(A) = \inf_n R_+(A^{\otimes n})^{1/n}. $$

We also note that the approximated version of the asymptotic nonnegative rank was studied in [23]. In that work, the authors showed that this notion captures the *common information* [24].

## B. Applications of asymptotic nonnegative rank

The asymptotic nonnegative rank can be interpreted as the *exact Rényi common information of order zero* [8]. This information is defined based on correlated sources (joint distribution), which is represented as a nonnegative matrix with normalized rows and columns. Specifically, given correlated sources $\pi_{XY}$ over $X \times Y$. The exact Rényi common information of order zero, denoted by $T_{Ex}^0(\pi_{XY})$, is the minimum common randomness rate for exact generation of the target distribution, with the constraint that common randomness can only be compressed using fixed-length codes. In [8], the authors showed that this information can be characterized by asymptotic nonnegative rank of $\pi_{XY}$. More precisely, they proved $T_{Ex}^0(\pi_{XY}) = \log \tilde{\mathbb{R}}_+(\pi_{XY})$. For more information about the exact Rényi common information, we refer to [25, Section 5 and Section 7].

In addition, the asymptotic nonnegative rank can be used as a lower bound for the *amortized communication complexity*. Unlike the original communication complexity (that we briefly introduce in the precedent paragraph), this model is interested in the minimum number of exchanging bits required to calculate a boolean function $f$ multiple times (on

different inputs $(x_i, y_i) \mid i = 1, \dots, m)$. A trivial upper bound for this quantity is $m$ times the complexity of calculating $f$ once. In other words, we obtain this complexity by simply calculating $f(x_i, y_i)$ separately, one after another. However, it turns out that in many computational models, the amortized communication complexity is smaller than this natural upper bound. It implies that the gain of complexity by performing calculation in batch can be significant. A notable example can be found in [9], where the author constructs a specific function $f$ whose communication complexity $D(f)$ and its amortization $\bar{D}(f)$ are totally different, i.e., $\bar{D}(f) < D(f)$. Using the result $\log R_+(M_f) \le D(f)$ of [3], we can prove a similar amortized counterpart, which states: $\log \tilde{R}_+(M_f) \le \bar{D}(f)$ (remind that $M_f$ is of size $|X| \times |Y|$, $M_f(x, y) = f(x, y)$). Therefore, the asymptotic nonnegative rank $\tilde{\mathbb{R}}_+$ is important for the study of amortized communication complexity.

## C. Contribution

In this paper, we consider the asymptotic spectra theory in the context of asymptotic nonnegative rank. Our main contributions are:

1) By introducing a nonnegative matrix semiring $M_+$ with two operators: $\oplus$ (the direct sum) and $\otimes$ (the Kronecker product) and a *preorder* $\le_+$ (cf. Definition 1), we define $\mathbf{X}(M_+, \le_+)$, the *asymptotic spectrum of* $M_+$. The set $\mathbf{X}(M_+, \le_+)$ consists of *monotone* semiring homomorphisms $\phi$ from the set of nonnegative matrices $M_+$ to the set of nonnegative numbers $\mathbb{R}_{\ge 0}$, i.e., if $A \le_+ B$, then $\phi(A) \le \phi(B)$ ($A, B$ are two nonnegative matrices). In fact, $\mathbf{X}(M_+, \le_+)$ is the nonnegative matrix version of other existing asymptotic spectra such as the asymptotic spectrum of tensors [10], graphs [13] and LOCC transformations [17], which are studied in the literature.

2) The definition of $\mathbf{X}(M_+, \le_+)$ allows us to establish another characterization of the asymptotic nonnegative rank of a matrix $A$ in Theorem 6, which states:

$$ \tilde{\mathbb{R}}_+(A) = \max_{\phi \in \mathbf{X}(S, \le_+)} \phi(A) $$

3) Similar to previous works on asymptotic spectra, we define and study two quantities: the *subrank* ($Q_+$) and *asymptotic subrank* ($\tilde{Q}_+$) of a nonnegative matrix. While $\tilde{Q}_+$ is a natural lower bound of $R_+$, $\tilde{Q}_+$ is the dual of $\tilde{R}_+$. In this work, we prove that $Q(A)$ is exactly equal to the induced matching number of the bipartite graph defined on the support of $A$ (see Theorem 8) and thus, independent of the coefficients of $A$. Moreover, similar to the asymptotic nonnegative rank, the asymptotic subrank can also be characterized by using $\mathbf{X}(M_+, \le_+)$ (cf. Theorem 6) as:

$$ \tilde{Q}_+(A) = \min_{\phi \in \mathbf{X}(S, \le_+)} \phi(A) $$

4) Since $\mathbf{X}(M_+, \le_+)$ allows us to characterize precisely $\tilde{\mathbb{R}}_+$ and $\tilde{Q}_+$, we study in detail the set $\mathbf{X}(M_+, \le_+)$. Our investigation of $\mathbf{X}(M_+, \le_+)$ consists of showing its two elements: the rank function and the fractional cover number
(cf. Section IV). We note that the construction of explicit elements in the asymptotic spectrum of a specific instance is nontrivial. For example, the construction of nontrivial (universal) elements in the asymptotic spectrum of tensors has been an open problem for more than thirty years until it was solved by recent work in [26].

All the missing proofs in this paper can be found in the full paper [27].

## II. ASYMPTOTIC SPECTRA AND STRASSEN'S SPECTRAL THEOREM

In this section, we present briefly the abstract theory of asymptotic spectra which was introduced by V. Strassen [10]. For a more complete presentation, we refer the readers to [10], [28], [11].

Let $(S, +, \cdot, 0_S, 1_S)$ be a commutative semiring, i.e., a set $S$ equipped with a binary addition operation $+$, a binary multiplication $\cdot$, and having two elements $0_S, 1_S \in S$ such that for all $a, b, c \in S$:

(1) $(S, +)$ is a commutative monoid with the identity element $0_S$.

(2) $(S, \cdot)$ is a commutative monoid with the identity element $1_S$.

(3) $\cdot$ distributes over $+$: $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$

(4) $0_S \cdot a = 0_S$.

For $n \in \mathbb{N}$ we denote the sum of $n$ elements $1_S$ by $n_S$, i.e., $n_S := 1_S + \cdots + 1_S \in S$. A *preorder* $\leq$ on $S$ is a relation on $S$ such that for all $a, b, c \in S$

1) $\leq$ is reflexive: $a \leq a$

2) $\leq$ is transitive: $a \leq b$ and $b \leq c$ implies $a \leq c$.

**Definition 1.** A *preorder* $\leq$ on $S$ is a *Strassen preorder* if

(i) For all $n, m \in \mathbb{N}$ $n \leq m$ iff $n_S \leq m_S$ in $S$.

(ii) For all $a, b, c, d \in S$ if $a \leq b$ and $c \leq d$, then $a+c \leq b+d$ and $a \cdot c \leq b \cdot d$.

(iii) For all $a, b \in S, b \neq 0$ there is $r \in \mathbb{N}$ such that $a \leq r_S \cdot b$.

Let $S$ be a commutative semiring and let $\leq$ be a Strassen preorder on $S$. Throughout the paper, we will use $\leq$ to denote the usual order on $\mathbb{R}$. Let $\mathbb{R}_{\geq 0}$ be the semiring of nonnegative real numbers. A semiring homomorphism from $S$ to $\mathbb{R}_{\geq 0}$ (denoted by $\operatorname{Hom}(S, \mathbb{R}_{\geq 0})$) is a map $\phi : S \to \mathbb{R}_{\geq 0}$ such that:

(1) $\phi(a \cdot b) = \phi(a)\phi(b)$

(2) $\phi(a+b) = \phi(a)+\phi(b)$

(3) $\phi(1_S) = 1$.

Let $\mathbf{X}(S, \leq)$ be the set of $\leq$-monotone semiring homomorphisms from $S$ to $\mathbb{R}_{\geq 0}$, i.e., $\mathbf{X}(S, \leq)$ equals

$$ \{\phi \in \operatorname{Hom}(S, \mathbb{R}_{\geq 0}) : \forall a, b \in S, a \leq b \Rightarrow \phi(a) \leq \phi(b)\}. $$

We note that for every $\phi \in \mathbf{X}(S, \leq)$ holds $\phi(1_S) = 1$ and thus $\phi(n_S) = n$ for all $n \in \mathbb{N}$. We call $\mathbf{X}(S, \leq)$ the *asymptotic spectrum* of $(S, \leq)$ and elements of $\mathbf{X}(S, \leq)$ *spectral points*.

Let $a \in S$, the rank of $a$ is defined as $\mathrm{R}(a) := \min\{n \in \mathbb{N} : a \leq n_S\}$. The subrank of $a$ is defined as $\mathrm{Q}(a) := \max\{n \in \mathbb{N} : n_S \leq a\}$.

The asymptotic subrank and asymptotic rank of $a$ are defined as

$$ \tilde{\mathrm{R}}(a) := \lim_{N \to \infty} \mathrm{R}(a^N)^{1/N} \quad \text{and} \quad \tilde{\mathrm{Q}}(a) := \lim_{N \to \infty} \mathrm{Q}(a^N)^{1/N} \qquad (2) $$

From Fekete's lemma, the limits in (2) indeed exist and can be replaced by an infimum and a supremum, that is,

$$ \tilde{\mathrm{R}}(a) = \inf_N \mathrm{R}(a^N)^{1/N}, \quad \text{and} \quad \tilde{\mathrm{Q}}(a) = \sup_N \mathrm{Q}(a^N)^{1/N}. $$

In [10], the author showed that the asymptotic rank and asymptotic subrank have the following dual characterization in terms of the asymptotic spectrum.

**Theorem 2** ([10, Th. 3.8] and [28, Cor. 2.14]). Let $S$ be a commutative semiring and let $\leq$ be a Strassen preorder on $S$. For any $a \in S$ such that $1_S \leq a$ and $2_S \leq a^k$ for some $k \in \mathbb{N}$, we have that

$$ \tilde{\mathrm{R}}(a) = \max_{\phi \in \mathbf{X}(S, \leq)} \phi(a), \quad \text{and} \quad \tilde{\mathrm{Q}}(a) = \min_{\phi \in \mathbf{X}(S, \leq)} \phi(a). $$

## III. ASYMPTOTIC SPECTRUM OF NONNEGATIVE MATRICES AND DUALITY

### A. Asymptotic spectrum of nonnegative matrices

In this section, our goal is to use the theory of the previous section to give the dual characterization of the asymptotic nonnegative rank of matrices. We remind the readers that $\otimes$ denotes the Kronecker product, $\oplus$ denotes the direct sum of matrices, and $I_n$ denotes the identity matrix of size $n \times n$.

A natural semiring can be defined by considering the set of nonnegative matrices equipped with the binary operators $\oplus$ and $\otimes$. However, the Kronecker product $\otimes$ is not commutative. Therefore, in the following construction, rather than working with the set of nonnegative matrices, we will work with its *quotient space* where $\oplus$ and $\otimes$ are commutative. In fact, we will introduce an equivalence relation in which equivalent elements share the same nonnegative rank, and the induced operators $\oplus/\otimes$ on the corresponding quotient space are commutative. This allows us to bypass the technical requirement and apply the theory of asymptotic spectra.

Denote by $\mathbb{M}(m, n)$ the set of all nonnegative matrices of size $m \times n$, for two nonnegative matrices $A, B \in \mathbb{M}(m, n)$, we write $A \cong B$ if there is a pair of matrices $(X, Y) \in \mathrm{GL}^+(m) \times \mathrm{GL}^+(n)$ such that $A = XBY^\top$ (or equivalently $B = X^{-1}A(Y^{-1})^\top$). It is clear that $\cong$ is an equivalence relation since if $A = X_1BY_1^T$, $B = X_2CY_2^T$, then $A = (X_1X_2)C(Y_1Y_2)^T$ with $X_1X_2 \in \mathrm{GL}^+(m)$, $Y_1Y_2 \in \mathrm{GL}^+(n)$.

Let $A \in \mathbb{M}(m_A, n_A)$ and $B \in \mathbb{M}(m_B, n_B)$, we say $A$ and $B$ are *equivalent*, and write $A \sim B$, if there are zero matrices $A_0 = 0 \in \mathbb{R}_+^{a_1 \times a_2}$ and $B_0 = 0 \in \mathbb{R}_+^{b_1 \times b_2}$ such that $A \oplus A_0 \cong B \oplus B_0$. Let $\mathbb{M}_+$ be the set of $\sim$-equivalence classes of nonnegative matrices, we define the addition and multiplication on $\mathbb{M}_+$ as follows

$$ [A] \oplus [B] = [A \oplus B], \quad [A] \otimes [B] = [A \otimes B], $$

where $[A]$ denotes the equivalence class of the matrix $A$.
**Lemma 3.** The set $M_+$ with addition $\oplus$, multiplication $\otimes$, additive unit $[0]$ and multiplicative unit $[I_1]$ is commutative semiring, where $[0]$ is the equivalence class of all zero matrices.

We write $A \leq_+ B$ if there are two nonnegative matrices $X \in \mathbb{R}_+^{m_A \times m_B}$ and $Y \in \mathbb{R}_+^{n_A \times n_B}$ such that $A = XBY^T$. This preorder ensures that if $A \leq_+ B$, then $R_+(A) \leq R_+(B)$. Note that $\leq_+$ is less restrictive than $\cong$ (which requires $X \in GL^+(m_A)$, $Y \in GL^+(n_A)$). This also implies that if $A \cong B$, then $A \leq_+ B$ and $B \leq_+ A$. The natural induced preorder of $\leq_+$ on $M_+$ is also well-defined in $M_+$, which is shown as follows:

**Lemma 4.** If $A \leq_+ B$, then $A' \leq_+ B'$, for all $A' \sim A, B' \sim B$.

Hereinafter, to ease the notation, we abuse the notations by writing $A$ to denote both the matrix $A$ and also the equivalence class $[A]$. The meaning should be clear from the context. The following lemma proves that $\leq_+$ is also a Strassen preorder.

**Lemma 5.** The preorder $\leq_+$ is a Strassen preorder on $M_+$. That is, for nonnegative matrices $A, B, C, D \in M_+$ we have the following.

(i) For all $n, m \in \mathbb{N}$, $n \leq m$ if and only if $I_n \leq_+ I_m$

(ii) If $A \leq_+ B$ and $C \leq_+ D$ then $A \oplus C \leq_+ B \oplus D$ and $A \otimes C \leq_+ B \otimes D$

(iii) If $B \neq 0$, there is an $r \in \mathbb{N}$ such that $A \leq_+ I_r \otimes B$.

We thus have a semiring $M_+$ with a Strassen preorder $\leq_+$. Thus, we can apply the theory of asymptotic spectra in this context. Let us translate the abstract terminology to this setting.

Let $S \subseteq M_+$ be a semiring. For example, one may take $S = M_+$, or one may choose any set $X \subseteq M_+$ and let $S = N[X]$ be the subsemiring of $M_+$ generated by $X$ under $\oplus$ and $\otimes$. The asymptotic spectrum of $S$ is the set $\mathbf{X}(S, \leq_+)$ of $\leq_+$-monotone semiring homomorphism $S \to \mathbb{R}_{\geq 0}$, i.e., all maps $\phi: S \to \mathbb{R}_{\geq 0}$ such that, for all $A, B \in S$

(1) $\phi(A \otimes B) = \phi(A)\phi(B)$

(2) $\phi(A \oplus B) = \phi(A) + \phi(B)$

(3) $\phi(I_n) = n$ for all $n \in \mathbb{N}$

(4) If $A \leq_+ B$ then $\phi(A) \leq \phi(B)$.

We call $\mathbf{X}(M_+, \leq_+)$ the asymptotic spectrum of nonnegative matrices. In the next subsection, we use the asymptotic spectrum of nonnegative matrices to give a dual characterization for asymptotic nonnegative rank.

## B. Asymptotic nonnegative rank and asymptotic nonnegative subrank

From Subsection III-A, we have shown that the preorder $\leq_+$ is a Strassen preorder. Thus, similar to Section II, using the preorder $\leq_+$, we can rewrite the nonnegative rank and define the nonnegative subrank of a nonnegative matrix $A$ as

$$R_+(A) := \min\{r \in \mathbb{N} : A \leq_+ I_r\}$$

$$Q_+(A) := \max\{q \in \mathbb{N} : I_q \leq_+ A\}.$$

Similarly to the asymptotic nonnegative rank, the asymptotic nonnegative subrank is naturally defined as follows.

$$\tilde{Q}_+(A) := \lim_{n \to \infty} Q_+(A^{\otimes n})^{1/n} = \sup_n Q_+(A^{\otimes n})^{1/n}.$$

Using the abstract theory of Strassen, the asymptotic spectrum of nonnegative matrices can be used to characterize the asymptotic nonnegative rank and the asymptotic nonnegative subrank.

**Theorem 6.** Let $A$ be a nonnegative matrix. Then

$$\tilde{R}_+(A) = \max_{\phi \in \mathbf{X}(M_+, \leq_+)} \phi(A), \text{ and } \tilde{Q}_+(A) = \min_{\phi \in \mathbf{X}(M_+, \leq_+)} \phi(A).$$

Before proceeding to the proof of Theorem 6, we need to show first a combinatorial interpretation of subrank $Q_+$. It is easy to see that the nonnegative rank of matrix $A$ depends on its entries. In the other direction, we show in the following that the nonnegative subrank of a nonnegative matrix depends only on its support. We first introduce some notions and preliminary results.

Let $A$ be a nonnegative matrix, we remind that $\text{supp}(A) = \{(i, j) : A_{i,j} > 0\}$ the support of $A$. Two pairs $(a, b)$, $(c, d) \in \text{supp}(A)$ is called totally pairwise independent if $A_{a,d} = A_{c,b} = 0$. A subset $\Phi$ of $\text{supp}(A)$ is called induced matching of $A$ if each pair $(a, b) \neq (c, d) \in \Phi$ is totally pairwise independent. The name induced matching here come from the fact that the totally pairwise independent set of matrix $A$ is an induced matching of the bipartite graph that construct from the support of $A$. We denote $\gamma(A)$ to be the size of largest induced matching of $A$. Let us illustrate this notion by the following example.

**Example 7.** Consider a binary matrix $A$ defined as:

$$A = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}.$$

It is easy to verify that in this example, $\psi = \{(1, 1), (2, 3), (3, 2), (4, 4)\}$ is not an induced matching of $A$ (since $A_{2,1} = 1 \neq 0$), and $\Phi = \{(4, 1), (3, 2)\}$ is an induced matching of $A$.

We show that for every nonnegative matrix, the largest size of an induced matching is equal to the nonnegative subrank, i.e.,

**Theorem 8.** For all nonnegative matrices $A$, $Q_+(A) = \gamma(A)$.

To prove Theorem 8, we first show two results: Proposition 9 and Proposition 10.

**Proposition 9.** For any nonnegative matrix $A$, we have $\gamma(A) \leq Q_+(A)$.

**Proposition 10.** Let $A, B, C$ be three nonnegative matrices such that $A = BC$, we have:

$$\gamma(A) \leq \min(\gamma(B), \gamma(C)).$$

We can now proceed to the proof of Theorem 8.
*Proof of Theorem 8.* From Proposition 9 we have $\gamma(A) \le Q_+(A)$ for any nonnegative matrix $A$. Suppose that $Q_+(A) = m$, we have $I_m = XAY^T$, from Proposition 10, one has

$$m = \gamma(I_m) = \gamma(XAY^T) \le \gamma(XA) \le \gamma(A).$$

That implies $\gamma(A) = Q_+(A) = m$. $\square$

<figure><img src="image_2.png" /></figure>

Theorem 8 characterizes a nice property of nonnegative subrank: it is equal to the maximum induced matching of the bipartite graph whose adjacency matrix is the support of its matrix. Finding the subrank of a matrix is thus reducible to the problem of finding the maximum induced matching of a bipartite graph. Unfortunately, the maximum induced matching problem is NP-hard, even in the setting of bipartite graph [29]. Even so, by using the properties of nonnegative matrices, we provide a combinatorial interpretation of the subrank of a nonnegative matrix. The subrank or symmetric subrank studied in other works [30], [31], [32], however, do not have this property. They depend on their coefficients.

With Theorem 8, we can now prove Theorem 6.

*Proof of Theorem 6.* There are two cases to consider:

1) If $A = 0$, then $\phi(A) = 0$ for any $\phi \in X(M_+, \le_+)$. The result follows trivially.

2) If $A \ne 0$, it is difficult to directly apply Theorem 2 since it is non-trivial to verify the condition: There exists an integer $k$ such that $I_2 \le_+ A^k$. In this proof, we provide a simple workaround: Instead of considering $A$, we consider $B := (A \oplus A)$. It is trivial that $I_2 \le_+ B^k$ with $k = 1$ because we assume that $A$ is non-zero. Therefore, using Theorem 2, we obtain:

$$\tilde{R}(B) = \max_{\phi \in X(S, \le)} \phi(B), \text{ and } \tilde{Q}(B) = \min_{\phi \in X(S, \le)} \phi(B).$$

Due to the definition of $X(S, \le)$, we have: $\phi(B) = 2\phi(A), \forall \phi \in X(S, \le)$. Thus, we can rewrite the above equation as:

$$\tilde{R}(B) = 2 \max_{\phi \in X(S, \le)} \phi(A), \text{ and } \tilde{Q}(B) = 2 \min_{\phi \in X(S, \le)} \phi(A). \quad (3)$$

It is thus, sufficient to show the two following equalities:

$$R_+(B^k) = 2^k R_+(A^k), \text{ and } Q_+(B^k) = 2^k Q_+(A^k).$$

Using definitions of $\tilde{R}_+$ and $\tilde{Q}_+$, we deduce that $\tilde{R}_+(B) = 2\tilde{R}_+(A)$ and $\tilde{Q}_+(B) = 2\tilde{Q}_+(A)$. Combining with Equation (3), we prove the theorem.

To this end, we first observe that:

$$B^k = (A \oplus A)^k = \underbrace{A^k \oplus \dots \oplus A^k}_{2^k \text{ times}}. \quad (4)$$

For the case of $R_+$, we will use the following claim: for every pair of nonnegative matrices $(X, Y)$, we have: $R_+(X \oplus Y) = R_+(X) + R_+(Y)$. The proof of this claim can be found in [27]. As a consequence of Equation (4), we have: $R_+(B^k) = 2^k R_+(A^k)$.

For the case of $Q_+$, thanks to Theorem 8, it is also clear that $Q_+$ is additive under $\oplus$, i.e., $Q_+(X \oplus Y) = Q_+(X) + Q_+(Y)$ for all nonnegative matrices $X, Y$. Indeed, the bipartite graph (corresponding to the support) of $(X \oplus Y)$ is the union of two disconnected bipartite graphs (corresponding to the support) of $X$ and $Y$ respectively. Thus, the maximum induced matching of $(X \oplus Y)$ is equal to the sum of these of $X$ and $Y$. Using the similar argument for $R_+$, we also have $Q_+(B^k) = 2^k Q_+(A^k)$. This concludes the proof. $\square$

<figure><img src="image_3.png" /></figure>

## IV. SOME ELEMENTS IN THE ASYMPTOTIC SPECTRUM OF NONNEGATIVE MATRICES

From Theorem 6, an explicit description of the asymptotic spectrum of nonnegative matrices is desired to understand the asymptotic nonnegative rank. However, the abstract theory of asymptotic spectra in Section II does not give an explicit construction of the elements of $X(M_+, \le_+)$. In this section, we show two elements that belong to the asymptotic spectrum of nonnegative matrices $X(M_+, \le_+)$ introduced in Section III, namely rank and fractional cover number.

**Lemma 11.** The matrix rank is an element of the asymptotic spectrum $X(M_+, \le_+)$.

The fractional cover number is a parameter of nonnegative matrices introduced by Lovász [33] to study the chromatic number of uniform hypergraphs.

We first remind readers of the definition of fractional cover number. Let $A \in \mathbb{R}_+^{m \times n}$ be a nonnegative matrix, a subset $X \times Y \subseteq [m] \times [n]$ is called monochromatic rectangle of the matrix $A$ if $X \times Y \subseteq \text{supp}(A)$. Let $R_1, \dots, R_k$ be all monochromatic rectangle of $A$. We define the fractional cover number of $A$, denoted $F(A)$, as follows

$$\begin{array}{ll} \text{minimize:} & \displaystyle \sum_{i=1}^{k} \tau(R_i) \\ \text{s.t} & \displaystyle \sum_{i:(a,b) \in R_i} \tau(R_i) \ge 1 \quad \text{for all } (a,b) \in \text{supp}(A) \\ & 0 \le \tau(R_i) \le 1 \quad \text{for all } i \in [k]. \end{array} \quad (5)$$

**Lemma 12.** The fractional cover number $F$ is an element of the asymptotic spectrum $X(M_+, \le_+)$.

## V. CONCLUSION AND FUTURE RESEARCH

We have formally defined the asymptotic spectrum of non-negative matrices and utilized it to provide a dual characterization of the asymptotic nonnegative rank of matrices. In future work, we plan to study the structure of the asymptotic spectrum of nonnegative matrices to explore algorithmic aspects in computing the asymptotic nonnegative rank.

## ACKNOWLEDGEMENT

The research of QTL is supported by the French "Investing for the Futurre - PIA3" program under the Grant agreement numbered ANR-19-PI3A-0004.
REFERENCES

[1] M. Yannakakis, "Expressing combinatorial optimization problems by linear programs," *Journal of Computer and System Sciences*, vol. 43, no. 3, pp. 441–466, 1991.

[2] E. Kushilevitz, "Communication complexity," in *Advances in Computers*, vol. 44, pp. 331–360, Elsevier, 1997.

[3] L. Lovász, "Communication complexity: A survey," *Paths, Flows, and VLSI-Layout*, p. 235, 1990.

[4] T. Lee, A. Shraibman, et al., "Lower bounds in communication complexity," *Foundations and Trends® in Theoretical Computer Science*, vol. 3, no. 4, pp. 263–399, 2009.

[5] A. Rao and A. Yehudayoff, *Communication Complexity: and Applications*. Cambridge University Press, 2020.

[6] S. Zhang, "Quantum strategic game theory," in *Proceedings of the 3rd Innovations in Theoretical Computer Science Conference*, pp. 39–59, 2012.

[7] R. Jain, Y. Shi, Z. Wei, and S. Zhang, "Efficient protocols for generating bipartite classical distributions and quantum states," *IEEE Transactions on Information Theory*, vol. 59, no. 8, pp. 5171–5178, 2013.

[8] L. Yu and V. Y. Tan, "On exact and $\infty$-rényi common informations," *IEEE Transactions on Information Theory*, vol. 66, no. 6, pp. 3366–3406, 2020.

[9] T. Feder, E. Kushilevitz, M. Naor, and N. Nisan, "Amortized communication complexity," *SIAM Journal on computing*, vol. 24, no. 4, pp. 736–750, 1995.

[10] V. Strassen, "The asymptotic spectrum of tensors.,", *J. Reine Angew. Math.*, vol. 384, pp. 102–152, 1988.

[11] A. Wigderson and J. Zuiddam, "Asymptotic spectra: Theory, applications and extensions," 2022.

[12] P. Bürgisser, M. Clausen, and A. Shokrollahi, *Algebraic Complexity Theory*, vol. 315. 01 1997.

[13] J. Zuiddam, "The asymptotic spectrum of graphs and the shannon capacity," *Combinatorica*, vol. 39, no. 5, pp. 1173–1184, 2019.

[14] Y. Li and J. Zuiddam, "Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum shannon capacities," *IEEE Transactions on Information Theory*, vol. 67, no. 1, pp. 416–432, 2020.

[15] M. U. Farooq, T. Fritz, E. Haapasalo, and M. Tomamichel, "Asymptotic and catalytic matrix majorization," *arXiv preprint arXiv:2301.07353*, 2023.

[16] R. Robere and J. Zuiddam, "Amortized circuit complexity, formal complexity measures, and catalytic algorithms," in *2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)*, pp. 759–769, IEEE, 2022.

[17] A. K. Jensen and P. Vrana, "The asymptotic spectrum of locc transformations," *IEEE Transactions on Information Theory*, vol. 66, no. 1, pp. 155–166, 2019.

[18] T. Fritz, "A generalization of strassen's positivstellensatz," *Communications in Algebra*, vol. 49, no. 2, pp. 482–499, 2021.

[19] P. Vrana, "A generalization of strassen's theorem on preordered semirings," *Order*, vol. 39, no. 2, pp. 209–228, 2022.

[20] L. B. Beasley, H. Klauck, T. Lee, and D. O. Theis, "Communication complexity, linear optimization, and lower bounds for the nonnegative rank of matrices (dagstuhl seminar 13082)," in *Dagstuhl Reports*, vol. 3, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.

[21] A. Vandaele, N. Gillis, F. Glineur, and D. Tuyttens, "Heuristics for exact nonnegative matrix factorization," *Journal of Global Optimization*, vol. 65, pp. 369–400, 2016.

[22] M. Fekete, "Über die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten," *Mathematische Zeitschrift*, vol. 17, no. 1, pp. 228–249, 1923.

[23] G. Braun, R. Jain, T. Lee, and S. Pokutta, "Information-theoretic approximations of the nonnegative rank," *computational complexity*, vol. 26, pp. 147–197, 2017.

[24] A. Wyner, "The common information of two dependent random variables," *IEEE Transactions on Information Theory*, vol. 21, no. 2, pp. 163–179, 1975.

[25] L. Yu and V. Y. F. Tan, "Common information, noise stability, and their extensions," *Foundations and Trends® in Communications and Information Theory*, vol. 19, no. 2, pp. 107–389, 2022.

[26] M. Christandl, P. Vrana, and J. Zuiddam, "Universal points in the asymptotic spectrum of tensors," in *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, pp. 289–296, 2018.

[27] Y. Meng Chee, Q. T. Le, and H. Ta, "On the asymptotic nonnegative rank of matrices and its applications in information theory," *arXiv e-prints*, pp. arXiv-2308, 2023.

[28] J. Zuiddam, *Algebraic complexity, asymptotic spectra and entanglement polytopes*. University of Amsterdam, 2018.

[29] K. Cameron, "Induced matchings," *Discrete Applied Mathematics*, vol. 24, no. 1-3, pp. 97–102, 1989.

[30] V. Strassen, "Degeneration and complexity of bilinear maps: Some asymptotic spectra.," *Journal für die reine und angewandte Mathematik*, vol. 413, pp. 127–180, 1991.

[31] M. Christandl, O. Fawzi, H. Ta, and J. Zuiddam, "Symmetric subrank of tensors and applications," *arXiv preprint arXiv:2104.01130*, 2021.

[32] M. Christandl, F. Gesmundo, and J. Zuiddam, "A gap in the subrank of tensors," *arXiv preprint arXiv:2212.01668*, 2022.

[33] L. Lovász, "On the ratio of optimal integral and fractional covers," *Discrete Mathematics*, vol. 13, no. 4, pp. 383–390, 1975.