Polynomials that preserve nonnegative monomial matrices

Benjamin J. Clark Pietro Paparella

(January 2, 2024)

Abstract

A recently-established necessary condition for polynomials that preserve the class of entrywise nonnegative matrices of a fixed order is shown to be necessary and sufficient for the class of nonnegative monomial matrices. Along the way, we provide a formula for computing an arbitrary power of a monomial matrix and a formula for computing the polynomial of a nonnegative monomial matrix.

1 Introduction

Motivated by the nonnegative inverse eigenvalue problem, Loewy and London [5] asked for a characterization of

\mathscr{P}_{n}\coloneqq\{p\in\mathbb{R}[t]\mid p(A)\geq 0,\ \forall A\in\mathsf{M}_{n}(\mathbb{R}),\ A\geq 0\}.

Clearly, $\mathscr{P}_{n}$ contains polynomials with nonnegative coefficients, but it is known that it contains polynomials having some negative entries.

The characterization of $\mathscr{P}_{1}$ is known as the Pólya–Szegö theorem, which asserts that $p\in\mathscr{P}_{1}$ if and only if

p(t)=\left(f_{1}(t)^{2}+f_{2}(t)^{2}\right)+t\left(g_{1}(t)^{2}+g_{2}(t)^{2}\right),

where $f_{1},f_{2},g_{1},g_{2}\in\mathbb{R}[t]$ (see, e.g., Powers and Reznick [7]).

Bharali and Holtz [1] gave partial results for the superset

\mathscr{F}_{n}\coloneqq\{f\ {\rm entire}\mid f(A)\geq 0,\ \forall A\in\mathsf{M}_{n}(\mathbb{R}),\ A\geq 0\}

of $\mathscr{P}_{n}$ , including a characterization of two-by-two matrices and results for certain structured nonnegative matrices, including upper-triangular matrices and circulant matrices.

More recently, Clark and Paparella [3] provided novel necessary conditions for $\mathscr{P}_{n}$ . In particular, they showed that the coefficients of a polynomial belonging to $\mathscr{P}_{n}$ satisfy certain linear inequalities. It was also shown [3, Corollary 4.5] that if $p\in\mathscr{P}_{n}$ , $r\in\{0,\ldots,n-1\}$ , $m\coloneqq\deg p$ , and $\mathcal{I}_{(m,n,r)}\coloneqq\{0\leq k\leq m\mid k\bmod{n}=r\}$ , then

p_{r}(t)=p_{(r,n)}(t)\coloneqq\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}t^{k}\in\mathscr{P}_{1}.

Since $\mathscr{P}_{k+1}\subseteq\mathscr{P}_{k}$ , $\forall k\in\mathbb{N}$ (see, e.g., Bharali and Holtz [1, Lemma 1]), it follows that

p_{(r,k)}\in\mathscr{P}_{1},\ \forall k\in\{1,\ldots,n\},\ \forall r\in\{0,\ldots,k-1\}.

(1)

In this work, condition (1) is shown to be sufficient for the class of nonnegative monomial matrices. In addition, a formula is given for computing the polynomial of a monomial matrix.

2 Notation

If $n\in\mathbb{N}$ , then $\mathsf{M}_{n}=\mathsf{M}_{n}(\mathbb{C})$ denotes the algebra of $n$ -by- $n$ matrices with complex entries and $S_{n}$ denotes the symmetric group of order $n$ . If $\sigma\in S_{n}$ and $x\in\mathbb{C}^{n}$ , then $\sigma(x)$ denotes the vector whose $i$ th-entry is $x_{\sigma(i)}$ and $P_{\sigma}\in\mathsf{M}_{n}$ denotes the permutation matrix corresponding to $\sigma$ (i.e., $P_{\sigma}$ is the the $n$ -by- $n$ matrix whose $(i,j)$ -entry is $\delta_{\sigma(i),j}$ , where $\delta_{ij}$ denotes the Kronecker delta). As is well-known, $\left(P_{\sigma}\right)^{-1}=P_{\sigma^{-1}}=\left(P_{\sigma}\right)^{\top}$ . When the context is clear, $P_{\sigma}$ is abbreviated to $P$ .

If $x\in\mathbb{C}^{n}$ , then $D_{x}\in\mathsf{M}_{n}$ denotes the diagonal matrix such that $d_{kk}=x_{k}$ , $1\leq k\leq n$ . If $A\in\mathsf{M}_{n}$ , then $A$ is called monomial, a monomial matrix, or a generalized permutation matrix if there is an invertible diagonal matrix $D=D_{x}$ and a permutation matrix $P$ such that $A=DP$ . The set of all $n$ -by- $n$ monomial matrices is denoted by $\mathsf{GP}_{n}=\mathsf{GP}_{n}(\mathbb{C})$ . If $A=D_{x}P$ , with $x\in\mathbb{C}^{n}$ , then

\alpha_{x}\coloneqq\det D_{x}=\prod_{k=1}^{n}x_{k}.

The restriction of $\mathscr{P}_{n}$ to the class of nonnegative monomial matrices is denoted by $\mathscr{P}_{n}^{\rm mon}$ .

If $n\in\mathbb{N}$ , then $\langle n\rangle\coloneqq\{1,\ldots,n\}$ , $\langle n\rangle_{0}\coloneqq\{0\}\cup\langle n\rangle$ , and $\pi=\pi_{n}:\langle n\rangle\longrightarrow\langle n\rangle$ is the permutation defined by $\pi(i)=(i\bmod{n})+1$ . The permutation matrix corresponding to $\pi$ is denoted by $C=C_{n}$ . i.e., $C=\left[\delta_{\pi(i),j}\right]\in\mathsf{M}_{n}$ . For example, if $n=3$ , then

\pi_{3}=\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}~{}\text{and}~{}C_{3}=\begin{bmatrix}0&1&0\\ 0&0&1\\ 1&0&0\end{bmatrix}.

If $x\in\mathbb{C}^{n}$ , then

K_{x}\coloneqq D_{x}C\in\mathsf{M}_{n}.

(2)

For example, if $x\in\mathbb{C}^{3}$ , then

K_{x}=\begin{bmatrix}0&x_{1}&0\\ 0&0&x_{2}\\ x_{3}&0&0\end{bmatrix}.

Definition 2.1 ([2, Definition 3.1]).

Let $p(t)=\sum_{k=0}^{m}a_{k}t^{k}\in\mathbb{C}[t]$ , $n\in\mathbb{N}$ , and $r\in\langle n-1\rangle_{0}$ . If

\mathcal{I}_{(m,n,r)}\coloneqq\{k\in\langle m\rangle_{0}\mid k\bmod{n}=r\},

then the polynomial

p_{(r,n)}(t)\coloneqq\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}t^{k},

(3)

is called the $r\bmod{n}$ -part of $p$ .

Remark 2.2.

If $m<n-1$ and $r>m$ , then $\mathcal{I}_{(m,n,r)}=\varnothing$ . In such a case, the sum on the right-hand side of (3) is empty. Consequently,

p_{(r,n)}(t)=\begin{cases}a_{r}t^{r},&0\leq r\leq m\\ 0,&m<r\leq n-1\end{cases}.

Observation 2.3 ([2, Observation 3.2]).

If $p\in\mathbb{C}[t]$ , then $p(t)=\sum_{r=0}^{n-1}p_{(r,n)}(t)$ .

3 Preliminary results

Johnson and Paparella [4, Lemma 3.3] used the relative gain array of a matrix to give a short proof of the elementary fact that if $x\in\mathbb{C}^{n}$ , then $D_{\sigma(x)}=P_{\sigma}D_{x}P_{\sigma}^{\top}$ , i.e.,

\displaystyle P_{\sigma}D_{x}=D_{\sigma(x)}P_{\sigma}.

(4)

Lemma 3.1 (Frobenius normal form for monomial matrices).

If $A\in\mathsf{GP}_{n}$ , then there is a permutation matrix $Q$ such that

\displaystyle Q^{\top}AQ=\bigoplus_{i=1}^{k}D_{y_{i}}C_{n_{i}}=\bigoplus_{i=1}^{k}K_{y_{i}},

(5)

where $1\leq k\leq n$ , $y=Q^{\top}x$ , and $y_{i}\in\mathbb{C}^{n_{i}}$ is the partition of $y$ into $k$ blocks of size $n_{i}$ for $i\in\langle{k}\rangle$ .

Proof.

By hypothesis, $A=D_{x}P$ and by the Frobenius normal form for permutation matrices (see, e.g., Paparella [6, Corollary 4.3]), there is a permutation matrix $Q=Q_{\gamma}$ such that

Q^{\top}PQ=\bigoplus_{i=1}^{k}C_{n_{i}},

where $1\leq k\leq n$ . If $y\coloneqq\gamma^{-1}(x)$ , where $y_{i}\in\mathbb{C}^{n_{i}}$ is the partition of $y$ into $k$ blocks of size $n_{i}$ for $i\in\langle{k}\rangle$ , then

	$\displaystyle Q^{\top}AQ$	$\displaystyle=\left(Q^{\top}D_{x}\right)PQ$
		$\displaystyle=\left(D_{y}Q^{\top}\right)PQ$
		$\displaystyle=D_{y}\left(Q^{\top}PQ\right)=D_{y}\bigoplus_{i=1}^{k}C_{n_{i}}=\bigoplus_{i=1}^{k}D_{y_{i}}C_{n_{i}}=\bigoplus_{i=1}^{k}K_{y_{i}}.\qed$

Lemma 3.2.

Let $x\in\mathbb{C}^{n}$ and let $j$ be a nonnegative integer. If $q\coloneqq\left\lfloor j/n\right\rfloor$ and $r=j\bmod{n}$ , then

K_{x}^{j}=\alpha_{x}^{q}\left(\prod_{j=0}^{r-1}D_{\pi^{j}(x)}\right)C^{r}.

(6)

Proof.

Proceed by induction on $j$ . For the base-case, if $j=0$ , then $q=r=0$ , and

K_{x}^{0}=I=\alpha_{x}^{0}\left(\prod_{j=0}^{-1}D_{\pi^{j}(x)}\right)K_{x}^{0},

given that the product on the right-hand side is empty and equal to $I$ .

For the induction-step, assume that the result holds when $j=\ell\geq 0$ and write $\ell=qn+r$ , where $0\leq r\leq n-1$ . Notice that

$\displaystyle K_{x}^{\ell+1}=K_{x}^{\ell}K_{x}$	$\displaystyle=\alpha_{x}^{q}\left(\prod_{j=0}^{r-1}D_{\pi^{j}(x)}\right)C^{r}D_{x}C$
	$\displaystyle=\alpha_{x}^{q}\left(\prod_{j=0}^{r-1}D_{\pi^{j}(x)}\right)D_{\pi^{r}(x)}C^{r}C$	(by (4))
	$\displaystyle=\alpha_{x}^{q}\prod_{j=0}^{r}D_{\pi^{j}(x)}C^{r+1},$

and if $0\leq r\leq n-2$ , then $r+1=(\ell+1)\bmod{n}$ and the result follows.

Otherwise, if $r=n-1$ , then $\ell+1=n(q+1)$ , $(\ell+1)\bmod{n}=0$ , and

\displaystyle K_{x}^{\ell+1}=\alpha_{x}^{q}\prod_{j=0}^{n-1}D_{\pi^{j}(x)}C^{n}=\alpha_{x}^{q}\prod_{j=0}^{n-1}D_{\pi^{j}(x)}C^{0}.

Given that $|\pi|=n$ (here, $|\cdot|$ denotes the order of $\pi$ as a group-element of $S_{n}$ ), the matrix

\prod_{j=0}^{n-1}D_{\pi^{j}(x)}=D_{\prod_{j=0}^{n-1}\pi^{j}(x)}

is a diagonal matrix such that every diagonal entry equals $\alpha_{x}$ . Thus,

K_{x}^{\ell+1}=\alpha_{x}^{q+1}\prod_{j=0}^{0}D_{\pi^{j}(x)}C^{0},

as desired. ∎

Remark 3.3.

If $0\leq r\leq n-1$ , then $\left\lfloor r/n\right\rfloor=0$ and applying (6) in this case yields

K_{x}^{r}=\left(\prod_{j=0}^{r-1}D_{\pi^{j}(x)}\right)C^{r}.

Thus, if $j$ is a nonnegative integer, $q\coloneqq\left\lfloor j/n\right\rfloor$ , and $r=j\bmod{n}$ , then $K_{x}^{j}=\alpha_{x}^{q}K_{x}^{r}$ .

4 Main results

Hereinafter, it is assumed that

p(t)=\sum_{k=0}^{m}a_{k}t^{k}\in\mathbb{R}[t],

where $a_{m}\not=0$ .

The following result gives a closed-form formula for computing the polynomial of a nonnegative monomial matrix.

Theorem 4.1.

If $x>0$ and $K_{x}$ is defined as in (2), then

p(K_{x})=\sum_{r=0}^{n-1}\frac{p_{(r,n)}(\alpha_{x}^{1/n})}{\alpha_{x}^{r/n}}K_{x}^{r}.

Proof.

If $k\in\mathcal{I}_{(m,n,r)}$ , then $k=q_{k}n+r$ where $0\leq r<n$ . By Lemma 3.2 and Observation 2.3 we have

\displaystyle p(K_{x})

\displaystyle=\sum_{r=0}^{n-1}p_{(r,n)}(K_{x})=\sum_{r=0}^{n-1}\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}K_{x}^{k}=\sum_{r=0}^{n-1}\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}\alpha_{x}^{q_{k}}K_{x}^{r}.

Finally, notice that

	$\displaystyle\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}\alpha_{x}^{q_{k}}$	$\displaystyle=\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}\frac{\alpha_{x}^{q_{k}+r/n}}{\alpha_{x}^{r/n}}$
		$\displaystyle=\frac{1}{\alpha_{x}^{r/n}}\sum_{k\in\mathcal{I}_{(m,n,r)}}a_{k}\alpha_{x}^{k/n}$
		$\displaystyle=\frac{p_{(r,n)}(\alpha_{x}^{1/n})}{\alpha_{x}^{r/n}},$

as desired. ∎

Corollary 4.2.

If $A=D_{x}P\geq 0$ with Frobenius normal form given by (5), then

\displaystyle p(A)=Q\left(\bigoplus_{i=1}^{k}\sum_{r=0}^{n_{i}-1}\frac{p_{(r,n_{i})}\left(\alpha_{x_{i}}^{1/n_{i}}\right)}{\alpha_{x_{i}}^{r/n_{i}}}K_{x_{i}}^{r}\right)Q^{\top}.

(7)

Proof.

Follows from Lemma 3.1, Theorem 4.1, and noting that for a matrix $A\in\mathsf{M}_{n}$ and permutation matrix $P$ we have $p\left(PAP^{\top}\right)=Pp(A)P^{\top}$ . ∎

Example 4.3.

A=\begin{bmatrix}0&3&0&0\\ 0&0&5&0\\ 0&0&0&2\\ 1&0&0&0\end{bmatrix}

and

p(t)=t^{20}+4t^{15}+2t^{8}+3t^{2}+t+5,

then, by Theorem 4.1,

	$\displaystyle p(A)$	$\displaystyle=\sum_{r=0}^{3}\frac{p_{(r,4)}(30^{1/4})}{30^{r/4}}A^{r}$
		$\displaystyle=p_{(0,4)}(30^{1/4})I_{4}+\frac{p_{(1,4)}(30^{1/4})}{30^{1/4}}A+\frac{p_{(2,4)}(30^{1/4})}{30^{1/2}}A^{2}+\frac{p_{(3,4)}(30^{1/4})}{30^{3/4}}A^{3}$
		$\displaystyle=(30^{5}+2\cdot 30^{2}+5)I_{4}+A+3A^{2}+30^{3}A^{3}.$

Theorem 4.4.

$p\in\mathscr{P}_{n}^{\rm mon}$ if and only if $p_{(r,k)}\in\mathscr{P}_{1},\ \forall k\in\langle n\rangle,\ \forall r\in\langle n-1\rangle_{0}$ .

Proof.

Since condition (1) is necessary for polynomials belonging to $\mathscr{P}_{n}$ (Clark and Paparella [3, Corollary 4.9]), it must also be necessary for polynomials belonging to $\mathscr{P}_{n}^{\rm mon}$ .

For sufficiency, if $A=D_{x}P\geq 0$ with Frobenius normal form given by (5), then $p(A)\geq 0$ in view of Corollary 4.2 and (7). ∎

References

[1] G. Bharali and O. Holtz. Functions preserving nonnegativity of matrices. SIAM J. Matrix Anal. Appl., 30(1):84–101, 2008.
[2] B. J. Clark and P. Paparella. Polynomials that preserve nonnegative matrices. Linear Algebra Appl., 637:110–118, 2022.
[3] B. J. Clark and P. Paparella. Polynomials that preserve nonnegative matrices of order two. Mathematics Exchange, 16:58–65, 2022.
[4] C. R. Johnson and P. Paparella. Perron spectratopes and the real nonnegative inverse eigenvalue problem. Linear Algebra Appl., 493:281–300, 2016.
[5] R. Loewy and D. London. A note on an inverse problem for nonnegative matrices. Linear and Multilinear Algebra, 6(1):83–90, 1978/79.
[6] P. Paparella. Frobenius normal forms of doubly stochastic matrices. Special Matrices, 7(1):213–217, 2019.
[7] V. Powers and B. Reznick. Polynomials that are positive on an interval. Trans. Amer. Math. Soc., 352(10):4677–4692, 2000.