Abstract
The spectral p-norm of r-matrices generalizes the spectral 2-norm of 2-matrices. In 1911 Schur gave an upper bound on the spectral 2-norm of 2-matrices, which was extended in 1934 by Hardy, Littlewood, and Pólya to r-matrices. Recently, Kolotilina, and independently the author, strengthened Schur's bound for 2-matrices. The main result of this paper extends the latter result to r-matrices, thereby improving the result of Hardy, Littlewood, and Pólya.
Abstract
The proof is based on combinatorial concepts like r-partite r-matrix and symmetrant of a matrix, which appear to be instrumental in the study of the spectral p-norm in general. Thus, another application shows that the spectral p-norm and the p-spectral radius of a symmetric nonnegative r-matrix are equal whenever p ≥ r. This result contributes to a classical area of analysis, initiated by Mazur and Orlicz back in 1930.
Abstract
Additionally, a number of bounds are given on the p-spectral radius and the spectral p-norm of r-matrices and r-graphs.
Introduction
In this paper we study the spectral p-norm of hypermatrices and its applications to spectral hypergraph theory. Recall that the spectral 2-norm A 2 of an m × n matrix A := a i,j is defined as Arguably, A 2 is the most important numeric parameter of A, so it is natural to compare it to other parameters of A. r i c j .
Introduction
Sometimes inequality (2) can be much stronger than (1); e.g., if A is the adjacency matrix of the star K 1,n , inequality (1) gives A 2 ≤ n, while (2) gives A 2 ≤ √ n, which is best possible, since A 2 = √ n. Let us add that an independent and shorter proof of inequality (2) was given also by the author in [23] .
Introduction
One of the goals of this paper is to extend inequality (2) to hypermatrices. Similar results can be traced back to Hardy, Littlewood, and Pólya's book "Inequalities" ( [15] , p. 196), where Schur's inequality (1) was extended in several directions. To state an essential version of this result in terms of hypermatrices, we introduce some terminology and notation.
Introduction
Let r ≥ 2, and let n 1 , . . . , n r be positive integers. An r-matrix of order n 1 × · · · × n r is a function defined on the Cartesian product [n 1 ] × · · · × [n r ] . If n 1 = · · · = n r = n, then A is called a cubical r-matrix of order n 1 , and [n] is called the index set of A.
Introduction
In this paper "matrix" stands for "r-matrix" with unspecified r; thus, ordinary matrices are referred to as 2-matrices. Matrices are denoted by capital letters, whereas their values are denoted by the corresponding lowercase letters with the variables listed as subscripts. E.g., if A is an r-matrix, we let a i 1 ,...,i r := A (i 1 , . . . , i r ) for all admissible i 1 , . . . , i r .
Introduction
Given an r-matrix A, any of the r! matrices obtained by permuting the variables of A is called a transpose of A. A cubical matrix is called symmetric if all its transposes are identical. Now, let A be an r-matrix of order n 1 × · · · × n r . We say that A is a rank-one matrix if there exist r vectors . 1 In graph theory the order of a (hyper)graph is the number of its vertices, and in much of matrix theory the order of a square matrix means the number of its rows. We keep these meanings.
Introduction
A central problem in analysis is the study of the critical points of |L A (x (1) , . . . , x (r) )|, subject to various constrains on x (1) , . . . , x (r) . Thus, following Lim [20] , for any real number p ≥ 1, define the spectral p-norm A p of A as A p := max {|L A (x (1) , . . . , x (r) )| : |x (1) 
Introduction
Here and further, |·| p stands for the l p norm of vectors and matrices. Let us stress that our definition of A p encompasses all real p ≥ 1, a fact that implies numerous subtle consequences. It is worth pointing out that the dual A * of the norm A 2 is called the nuclear norm of A 2 . Next, we generalize the rows and columns of 2-matrices: Let A be an r-matrix of order Further, for every k ∈ [r] , let .
Introduction
Clearly, inequality (4) extends Schur's bound to r-matrices, but it does not extend Kolotilina's inequality (2) in any way. Thus, we propose a bound that extends (2) and strengthens (4):
Introduction
Once again, the adjacency matrices of β-stars 3 (see [2] , p. 116) show that (5) can be essentially better than (4) .
Introduction
Our proof of Theorem 1 turned out to be much more difficult than the proof of (2), and needs a multistage preparation, starting basically from scratch. To explain the main idea of our approach, let A be a real 2-matrix and set
Introduction
2 The nuclear norm is fundamental for tensor products of Banach spaces. It was introduced quite a while ago by Schatten [31] and Grothendieck [14] , but is enjoying a renewed interest presently; see, e.g., [8] , [12] , [13] , [19] , and [21] .
Introduction
3 β-stars are hypergraphs such that all edges share the same vertex and no two edges share other vertices.
Introduction
It is known (see, e.g., [16] , p. 418) that the nonzero singular values of A are precisely the positive eigenvalues of B; in particular, A 2 is the maximal eigenvalue of B. The matrix B has been extended to r-matrices by Ragnarsson and Van Loan in [29] . We establish some properties of this extension, eventually obtaining a proof of Theorem 1. These results turn out to be useful also for other problems; in particular, to make some progress in a classical area of analysis started by Mazur and Orlicz around 1930, see [30] , p 143. To convey the gist of this topic, we need two more definitions: Given a real symmetric matrix A of order n, the polynomial form P A of A is a function P A : R n → R defined for any vector x := (x 1 , . . . , x n ) as
Introduction
Further, for any real p ≥ 1, define the p-spectral radius η (p) (A) of A as
Introduction
Clearly, for any p ≥ 1, we have η (p) (A) ≤ A p , but equality rarely holds. In fact, the relations between η (p) (A) and A p have been studied for almost nine decades by now, albeit under no special names. In particular, motivated by problem 73 of Mazur and Orlicz in [30] , Banach [1] proved a result that implies the following basic fact:
Introduction
Theorem If A is a real symmetric r-matrix of order n, then
Introduction
For newer proofs of Banach's result, see [10] and [26] , and for further results, see [7] and [26] , and their references. Nonetheless, this area still holds surprises, as seen in the following theorem:
Introduction
Theorem 2 If A is a nonnegative symmetric r-matrix and p ≥ r, then
Introduction
As mentioned above, Theorem 2 is proved in the same combinatorial framework as Theorem 1, but its proof also needs a supporting Perron-Frobenius mini-theory. It is possible that the following stronger assertion holds:
Introduction
Conjecture 3 For every integer r ≥ 3, there is a p 0 (r) ∈ (1, 2) such that if A is a nonnegative symmetric r-matrix, then η (p) (A) = A p for every p ≥ p 0 (r) .
Introduction
The remaining part of the paper is split into three sections: in Section 2, we present relevant definitions and lay the basis for the proofs of Theorems 1 and 2. Section 3 contains the proof of Theorem 1 and several bounds on the spectral p-norm, conceived in the spirit of spectral graph theory. Finally, Section 4 lists some consequences of the main theorems for hypergraphs.
Collecting some spectral tools for hypermatrices
In this section we assemble the machinery that is needed for the proofs of Theorems 1 and 2. Although these proofs are our primary goal, we address broader topics involving A p and η (p) (A) , and explore many sidetracks as well. The section is rather long, so we outline its main topics first: Section 2.1 presents elemental properties of A p as a function of p. In Section 2.2, we discuss real symmetric matrices and their polynomial forms. Section 2.3 presents the basics on eigenequations. In Section 2.4, we build a Perron-Frobenius mini-theory, since the existing Perron-Frobenius theory of nonnegative hypermatrices is not sufficient for the proofs of Theorem 1 and 2. Sections 2.5 and 2.6 introduce the new concepts "r-partite rmatrix" and "symmetrant", both of which are crucial for our study of A p . Section 2.6 concludes with the proof of Theorem 2.
Basic properties of A p
Let A be an r-matrix of order n 1 × · · · × n r . If the vectors
Basic properties of A p
Since A p is defined for every real p ≥ 1, it is useful to investigate the function h A (x) = A x for fixed A and x ≥ 1. Set |A| max = max i 1 ,...,i r |a i 1 ,...,i r |, and note a few properties of A p :
Proposition 4
If A is an r-matrix of order n 1 × · · · × n r , then A p has the following properties:
Proposition 4
Proof (a) Let |A| max = |a i 1 ,...,i r |, and for any k ∈ [r] , let
Proposition 4
= 1 and zero elsewhere. Hence, |A| max = |L A (x (1) , . . . , x (r) )| ≤ A 1 . On the other hand,
Proposition 4
(b) Let x (1) , . . . , x (r) be an eigenkit to A q . Since the entries of x (1) , . . . , x (r) are of modulus at most one and p/q ≥ 1, it turns out that |x ( 
Proposition 4
, . . . , 1
Proposition 4
(c) Let x (1) , . . . , x (r) be an eigenkit to A p . The Power Mean inequality implies that
Proposition 4
, and note that |y (k) | q ≤ 1. Therefore,
Proposition 4
. . , x (r) be an eigenkit to A q . We see that
Proposition 4
(e) Let p > q ≥ 1. Clauses (c) and (d) imply that
Proposition 4
In view of (n 1 · · · n r ) 1/θ θ −2 < n 1 · · · n r , the required inequality follows, completing the proof of Proposition 4.
Proposition 4
Since A p is nondecreasing and bounded in p, the limit lim p→∞ A p exists. It is not hard to see that if A is nonnegative, then lim p→∞ A p = |A| 1 , but in general the value of this limit is not clear, so we raise a problem: 
Real symmetric matrices
Given an n-vector x and a set X ⊂ [n] , write x| X for the restriction of x over the set X in the order induced by [n] . Further, for any real number p ≥ 1, write S n−1 p for the set of all real
Real symmetric matrices
The values λ (r) (A), λ min (A) have been extensively studied-see [24] and its references.
Real symmetric matrices
Let p ≥ 1, and let λ ∈ {λ (p) (A) , λ
Real symmetric matrices
is called an eigenvector to λ. Note that if p = r, the norms of the eigenvectors to λ (p) (A) and
Real symmetric matrices
Note two fundamental identities about the polynomial form of A:
Real symmetric matrices
For the sake of applications, it is useful to investigate the function h A (x) = η (x) (A) for fixed symmetric matrix A and x ≥ 0. Here we state a few properties of λ (p) (A) , which can be proved as in Proposition 4: Proposition 7 If A is a real symmetric r-matrix of order n, then η (p) (A) has the following properties:
Eigenequations
Let A be a cubical r-matrix of order n. Following [27] and [6] , we say that a complex number λ is an eigenvalue of A if
Eigenequations
for some nonzero complex vector (x 1 , . . . , x n ), called an eigenvector to λ. Recently, eigenvalues of r-matrices have been studied intensively and have been put on a solid ground (see, e.g., [27] and [17] ). We shall not need this whole theory except the concept of spectral radius. Recall that the spectral radius ρ (A) of a cubical matrix A is the largest modulus of an eigenvalue of A. As we shall see, if A is a symmetric nonnegative matrix, then
Eigenequations
However, if r > 2, this identity may not hold for arbitrary real symmetric r-matrices. Next, we show that λ (p) (A) and λ
(p)
min (A) satisfy a system of equations similar to (9) . Suppose that A is a real symmetric r-matrix of order n and let x := (x 1 , . . . , x n ) ∈ S n−1 p be an eigenvector to λ (p) (G). If p > 1, the function |x 1 | p + . . . + |x n | p has continuous derivatives in each variable x i . Thus, Lagrange's method implies that there exists a µ such that for each
(p)
Now, multiplying the kth equation by x k and adding all equations, we find that
(p)
Hence, we arrive at the following theorem:
(p)
Theorem 8 Let A be real symmetric r-matrix of order n and let p > 1.
(p)
min (G)} and x := (x 1 , . . . , x n ) ∈ S n−1 p is an eigenvector to λ, then x 1 , . . . , x n satisfy the equations
(p)
Starting with equations (10), it is possible to introduce a new class of eigenvalues, but we do not pursue this direction here, except for a simple proposition needed for the proof of Theorem 16. Recall that in [28] , Qi showed that if A is a symmetric nonnegative r-matrix, then η (r) (A) is an eigenvalue of A of largest modulus, that is to say, η (r) (A) = ρ (A). It turns out that a similar statement holds for η (p) (A) for any p > 1 : Proposition 9 Let A be a symmetric nonnegative r-matrix and let p > 1. If λ ∈ R and x := (x 1 , . . . , x n ) ∈ S n−1 p satisfy the equations
(p)
and λ satisfy the equations (11), then
(p)
Adding all inequalities together, we find that
(p)
completing the proof.
A Perron-Frobenius mini-theory
The combined work of Chang, Pearson, and Zhang [6] , Friedland, Gaubert, and Han [11] , and Yang and Yang [33] laid the ground for a Perron-Frobenius theory of nonnegative hypermatrices. Roughly speaking this theory studies ρ (A) of nonnegative cubical r-matrices and its eigenvectors. However, for symmetric nonnegative r-matrices the parameter η (p) (A) is more general than ρ (A), and the existing Perron-Frobenius theory does not cover η (p) (A) for p = r. Thus, in this section we give some new Perron-Frobenius type theorems, which are necessary for our proofs. Note that if A is a symmetric nonnegative matrix, then η (p) (A) = λ (p) (A) , so these two values can be used interchangeably.
A Perron-Frobenius mini-theory
The digraph D (A) of a cubical r-matrix of order n is defined by setting V (D (A)) := [n] and letting {k, j} ∈ E (D (A)) whenever there is a nonzero entry a k,i 2 ,...,i r such that j ∈ {i 2 , . . . , i r }. Following [11] , a cubical matrix is called weakly irreducible if its digraph is strongly connected; if a cubical matrix is not weakly irreducible, it is called weakly reducible.
A Perron-Frobenius mini-theory
In analogy to 2-matrices, given a cubical r-matrix A of order n and a set X ⊂ [n], we write A [X] for the cubical matrix that is the restriction of A over X, and call A [X] a principal submatrix of A induced by X.
A Perron-Frobenius mini-theory
Clearly the digraph D (A) of a symmetric matrix A is an undirected 2-graph. If A is a weakly reducible symmetric matrix, then D (A) is disconnected and the vertices of each component of D (A) induce a weakly irreducible principal submatrix of A, called a component of A. Obviously, a symmetric matrix is a block diagonal matrix of its components.
A Perron-Frobenius mini-theory
Our first theorem is typical for this area, but still holds a small surprise, because it is valid for p > r − 1, whereas all known similar statements require that p = r. We find this fact a vindication for the study of η (p) (A) for any real p ≥ 1.
A Perron-Frobenius mini-theory
Theorem 10 Let r ≥ 2, p > r − 1, A be a symmetric nonnegative r-matrix, and x be a nonnegative eigenvector to λ (p) (A) . If A is weakly irreducible, then x is positive.
A Perron-Frobenius mini-theory
Proof Assume for a contradiction that x := (x 1 , . . . , x n ) has zero entries, and set Z := {i : x i = 0}. Since A is weakly irreducible, there exist i 1 , . . . , i r such that a i 1 ,...,i r > 0 and
A Perron-Frobenius mini-theory
To finish the proof we shall construct a vector y ∈ S n−1 p,+ such that P A (y) > P A (x) = λ (p) (G) , which yields the desired contradiction. Let k ∈ W, and for every sufficiently small ε > 0,
A Perron-Frobenius mini-theory
and δ (ε) → 0 as ε → 0. Since x j > 0 for each j ∈ W, we may and shall assume that δ < min j∈W x j /2 and ε < min
A Perron-Frobenius mini-theory
Now, define the vector y := (y 1 , . . . , y n ) by
A Perron-Frobenius mini-theory
First, (12) and (13) imply that |y| p = |x| p = 1 and y ≥ 0. Also, Bernoulli's inequality implies
A Perron-Frobenius mini-theory
, and so,
A Perron-Frobenius mini-theory
Further, referring to (7), set for short
A Perron-Frobenius mini-theory
and note that a j 1 ,...,j r x j 1 · · · x j r = a j 1 ,...,j r y j 1 · · · y j r whenever k / ∈ {j 1 , . . . , j r } . Hence
A Perron-Frobenius mini-theory
On the other hand,
A Perron-Frobenius mini-theory
, and, taking into account (14), we get
A Perron-Frobenius mini-theory
In view of p − r + 1 > 0, if ε is sufficiently small, then P A (y) − P A (x) > 0, contradicting the inequality P A (y) ≤ P A (x) , and completing the proof.
A Perron-Frobenius mini-theory
Next, we prove another somewhat surprising fact, which asserts that if p > r, then η (p) (A) of a symmetric nonnegative r-matrix A depends on all nonzero components of A:
A Perron-Frobenius mini-theory
Theorem 11 Let p > r ≥ 2 and let A be a symmetric nonnegative r-matrix. If A 1 , . . . , A k are the nonzero components of A, then
A Perron-Frobenius mini-theory
Proof Clearly, we may assume that A has no zero slices. Suppose that N 1 , . . . , N k are the index sets of A 1 , . . . , A k , let x be a nonnegative eigenvector to λ (p) (A) , and set
A Perron-Frobenius mini-theory
Letting s = p/r and t = p/ (p − r) , we see that
A Perron-Frobenius mini-theory
Now, Hölder's inequality implies that
A Perron-Frobenius mini-theory
To finish the proof of (15), we need to prove the opposite inequality.
A Perron-Frobenius mini-theory
. Now, define a vector u piecewise, by letting u be equal to z i within N i for each i = 1, . . . , k . We see that |u| p = 1 and
A Perron-Frobenius mini-theory
, completing the proof of (15).
A Perron-Frobenius mini-theory
Clearly, Theorems 10 and 11 imply the following simple corollary:
A Perron-Frobenius mini-theory
Corollary 12 Let p > r ≥ 2 and let A be a symmetric nonnegative r-matrix with no zero slices. If x is a nonnegative eigenvector to λ (p) (A) , then x is positive.
A Perron-Frobenius mini-theory
Next, we show that if A is a symmetric nonnegative r-matrix and p ≥ r, then λ (p) (G) is the only eigenvalue with a positive eigenvector. This fact is known for p = r (see, e.g., [33] ).
Proposition 13
Let p ≥ r ≥ 2, and let A be a symmetric nonnegative r-matrix of order n. If x := (x 1 , . . . , x n ) is a positive vector with |x| p = 1, satisfying the equations
Proposition 13
Proof Let y := (y 1 , . . . , y n ) be a nonnegative eigenvector to λ (p) (A) and let σ := min {x i /y i : y i > 0} .
Proposition 13
Clearly σ > 0 and also σ ≤ 1, for otherwise |x| p > |y| p , a contradiction. Note that x i ≥ σy i for every i ∈ [n] . Since x k = σy k for some k ∈ [n] , we see that
Proposition 13
On the other hand, Proposition 9 implies that λ ≤ λ (p) (A) , and so λ = λ (p) (A) .
Proposition 13
For the proof of Theorem 17 we also need another well-known fact, which is proved here for completeness. Note that it is valid for any cubical nonnegative r-matrix, not necessarily symmetric.
Proposition 14
Let A be a nonnegative cubical matrix of order n. If (x 1 , . . . , x n ) is a nonnegative nonzero vector, then there is a k ∈ [n] such that
Proposition 14
Proof The assertion is obvious if (x 1 , . . . , x n ) has zero entries. Thus, let x := (x 1 , . . . , x n ) be a positive vector. The Perron-Frobenius theory developed in [6] , [11] , and [33] implies that ρ (A) is an eigenvalue of A, and it has a nonnegative eigenvector (y 1 , . . . , y n ). 
r-partite r-matrices
Bipartite graphs are fundamental building blocks in structural theorems for 2-graphs, like, e.g., in Szemerédi's Regularity Lemma. For r-uniform hypergraphs a similar role is played by the r-partite r-graphs. This concept can be extended to matrices, so in this section we define r-partite r-matrices and prepare the introduction of the symmetrant of a matrix. Both these concepts are based on partitions of the index set of cubical matrices. ∈ N η(x) , and let θ (x) be the relative position of x in the set N η(x) , in the ordering induced by [n] .
r-partite r-matrices
A cubical r-matrix A of order n is called r-partite if there is a partition [n] = N 1 ∪ · · · ∪ N r with selector η (x) such that if a i 1 ,...,i r = 0, then η (i 1 ) , . . . , η (i r ) are distinct. E.g., a square 2-matrix is bipartite if after a permutation of its index set, it can be written as a block matrix
r-partite r-matrices
where the zero diagonal blocks are square.
r-partite r-matrices
Here is a crucial theorem, which seems new even for bipartite 2-matrices. For bipartite graphs and p = 2 it was proved in [4] by another method. 
r-partite r-matrices
Assume that the conclusion of the theorem fails for some i ∈ [r] , which obviously implies that |x (1) | p < |x (r) | p . Let α := |x (r) | p /|x (1) | p , and β := |x (1) | p /|x (r) | p , and define an n-vector y by setting y| N 1 := αx (1) , y| N r := βx (r) and letting y be the same as x over the set N 2 ∪ · · · ∪ N r−1 . First, note that |y| p < 1. Indeed,
r-partite r-matrices
On the other hand, αβ = 1, and so, Hence, y is an eigenvector to ρ (p) (A) . However, ||y| −1 p y| p = 1, and so
r-partite r-matrices
This contradiction completes the proof.
The symmetrant of a matrix
In this section we discuss the symmetrant of a matrix, a concept that has been introduced by Ragnarsson and Van Loan in [29] .
The symmetrant of a matrix
Suppose that A is a real r-matrix of order n 1 × · · · × n r . Set n := n 1 + · · · + n r , partition [n] into r consecutive intervals N 1 , . . . , N r with |N 1 | = n 1 , . . . , |N r | = n r , and let η (x) and θ (x) be the selector and the locator of this partition. Now, define an r-matrix B of order n by
The symmetrant of a matrix
The matrix B will be called the symmetrant of A and will be denoted by sym(A). The correspondence (j 1 , . . . , j r ) → (i 1 , . . . , i r ) in (17) can be described also as follows: if j 1 , . . . , j r belong to different sets N 1 , . . . , N r , then reorder j 1 , . . . , j r into j ′ 1 , . . . , j ′ r so that η (j ′ s ) increases with s, and let Proof (a) Suppose that A is a matrix of size n 1 × · · · × n r , set n := n 1 + · · · + n r , partition [n] into r consecutive intervals N 1 , . . . , N r with |N 1 | = n 1 , . . . , |N r | = n r , and let η (x) and θ (x) be the selector and the locator of this partition.
The symmetrant of a matrix
Let x be a real n-vector and let x (1) := x| N 1 , . . . , x (r) := x| N r . It is not hard to check the identity
The symmetrant of a matrix
, . . . , x (r) ). , . . . ,
The symmetrant of a matrix
, . . . , x r ). 
The symmetrant of a matrix
and therefore,
The symmetrant of a matrix
, . . . , x (r) )| ≤ r! r r/p A p , proving (18) .
The symmetrant of a matrix
(b) Suppose that A is nonnegative and let x (1) , . . . , x (r) be an eigenkit to A p . Note that in general x (1) , . . . , x (r) may be complex vectors, but we suppose that they are nonnegative, because
The symmetrant of a matrix
Lagrange's method implies that for any k ∈ [r] , there exists a µ k such that for every s ∈ [n k ],
Multiplying this equation by x (k)
s , and adding all equations for s ∈ [n k ], we see that
Multiplying this equation by x (k)
, . . . , x (r) ) = A p .
Multiplying this equation by x (k)
Hence µ k = A p for every k ∈ [r]. Next, write x for the n-vector defined piecewise by x| N 1 := x (1) , . . . , x| N r := x (r) . Let y := r −1/p x, and note that |y| p = 1. Suppose that i ∈ [n], and set k := η (i) and s := θ (i). Clearly,
Multiplying this equation by x (k)
and (19) implies that
Multiplying this equation by x (k)
Therefore, Proposition 9 implies that
Multiplying this equation by x (k)
completing the proof of Theorem 16.
Multiplying this equation by x (k)
Armed with Theorem 16 and the results of Section 2.4, we encounter no difficulty in proving Theorem 2.
Proof of Theorem 2
Suppose that A is symmetric and nonnegative r-matrix of order n. First, we prove the assertion for p > r, and then obtain the case p = r by passing to limit. Thus, suppose that p > r and let x be an eigenvector to λ (p) (A) , which by Corollary 12 is positive. Let n ′ = rn, and suppose that [n ′ ] = N 1 ∪ · · · ∪ N r is the partition of sym (A). Write y for the n-vector defined piecewise by y| N 1 := x, . . . , y| N r := x. Let z := r −1/p y, and note that |z| p = 1. Following the argument of clause (b) of Theorem 16, we conclude that
Proof of Theorem 2
and therefore,
Proof of Theorem 2
On the other hand, Propositions 4 and 7 imply that λ (p) (A) and A p are continuous in p, so letting p → r, we see that
Proof of Theorem 2
completing the proof of Theorem 2.
Bounds on the spectral p-norm of matrices
In this section we use results from the previous sections to prove various bounds on the spectral norms of r-matrices. Motivated by a well-known and very usable bound for 2-graphs, in Section 3.1 we give an upper bound on A p , which helps to conclude the proof of Theorem 1, but is also of independent interest. In Section 3.2, we give a few general bounds on A p , in particular, bounds related to regular matrices.
An upper bound on A r and a proof of Theorem 1
The main purpose of this section is to prove a combinatorial bound on A r , and apply this bound to prove Theorem 1.
An upper bound on A r and a proof of Theorem 1
Suppose that A is an m × n nonnegative 2-matrix. Recall that A 2 2 is the largest eigenvalue of AA T and A T A; hence A 2 2 does not exceed either of the maximum rowsums of AA T and A T A, i.e.,
An upper bound on A r and a proof of Theorem 1
In the next theorem we generalize this bound to r-matrices: Theorem 17 If A is an r-matrix of order n 1 × · · · × n r , then
An upper bound on A r and a proof of Theorem 1
Proof Since A r ≤ |A| r , without loss of generality, we assume that A is nonnegative. Thus, letting B := sym (A) , Theorem 16 implies that
An upper bound on A r and a proof of Theorem 1
For any i ∈ [n] , set
An upper bound on A r and a proof of Theorem 1
Without loss of generality we assume that A has no zero slices; thus, B has no zero slices either; hence, d i > 0 for every i ∈ [n.] . Letting k := η (i) and s = θ (i), it is not hard to see that
An upper bound on A r and a proof of Theorem 1
1/r n ), and observe that Proposition 14 implies that for some i ∈ [n] ,
An upper bound on A r and a proof of Theorem 1
Dividing both sides by (r − 1)! and using Theorem 16, we find that
An upper bound on A r and a proof of Theorem 1
In view of the identity
An upper bound on A r and a proof of Theorem 1
the Power Mean Inequality implies that
An upper bound on A r and a proof of Theorem 1
and so
An upper bound on A r and a proof of Theorem 1
Letting k = η (i) and s = θ (i) , it is not hard to see that for each j ∈ [r] \ {k} , there exists
An upper bound on A r and a proof of Theorem 1
and inequality (20) follows.
An upper bound on A r and a proof of Theorem 1
Using Theorem 17, just a minor extra effort is needed to prove Theorem 1. Note that our proof extends the idea of [23] , which is different from the main idea of Kolotilina [18] .
Proof of Theorem 1
Since A r ≤ |A| r , without loss of generality, we assume that A is nonnegative, and so Theorem 17 implies that
Proof of Theorem 1
Let the extremum in the right side be attained for k ∈ [r] and s ∈ [n k ] . Then
Proof of Theorem 1
completing the proof of Theorem 1. 4
A few general bounds on A p
In this subsection, first we study real symmetric matrices with constant slice sums, which have some extremal spectral properties. Thus, write ΣA for the sum of the entries of a matrix A. An r-matrix A of order n 1 × · · · × n r is called regular, if for every k ∈ [r] ,
A few general bounds on A p
Note that the adjacency matrix of a regular 2-graph G is regular, and so is the biadjacency matrix of a semiregular bipartite 2-graph; these facts explain our choice for the term "regular". As with 2-matrices, it turns out that regularity is closely related to the spectral radius:
A few general bounds on A p
Proposition 18 If A is a real symmetric r-matrix of order n and η (p) (A) = n −r/p |ΣA| for some p > 1, then A is regular.
A few general bounds on A p
min (G)} and η (p) (A) = |λ| = n −r/p |ΣA| = P A n −1/p j n . Then λ satisfies the equations
A few general bounds on A p
where ε = ±1. Therefore ΣA
A few general bounds on A p
n k , and so A is regular.
A few general bounds on A p
Moreover, if A is nonnegative and p ≥ r, the converse of Proposition 18 is true as well:
A few general bounds on A p
Theorem 19 Let p ≥ r and A be a nonnegative symmetric r-matrix of order n. If A is regular, then η (p) (A) = n −r/p ΣA.
Proof
Recall that if p ≥ r and A is nonnegative symmetric, then
Proof
be a nonnegative eigenvector to λ (p) (A) , and suppose that x k = max {x 1 , . . . , x n } . Since Lagrange's method implies that
Proof
and we have x k ≥ n −1/p , it follows that
Proof
we conclude that η (p) (A) = n −r/p ΣA.
Proof
Next, we give bounds on A p , which generalize well-known facts about the 2-spectral norm of 2-matrices.
Proof
On the other hand, equality holds in (23) , and so the complex arguments of all nonzero terms a i 1 ,...,i r x
Proof
are the same, that is to say, there exists c ∈ [0, 2π) such that arg(a i 1 ,...,i r x
Proof
Hence, a i 1 ,...,i r = y
Proof
. . , i r ∈ [n r ], and so A is a rank-one matrix.
Proof
In particular, Theorem 20 implies that
Proof
for any r-matrix A, which was shown (without the case of equality) by Friedland and Lim in [12] . On the other hand, Proposition 4, (a) states that
Proof
so (22) holds for p = 1 as well, but not the characterization of equality. Next, we prove some lower bounds on A p :
Proof
Theorem 21 Let p ≥ 1 and A be an r-matrix of order Proof (a) We outline the proof of (24) for k = r; for other values of k the proof is similar.
Proof
Letting Clearly, |x (r) | p = 1; thus
Proof
(b) Suppose that A is nonnegative and that equality holds in (24) for every k. Clearly, letting
Proof
, we obtain an eigenkit to A p , because
Proof
. It turns out that x (1) , . . . , x (r) are a solution to the constrained optimization problem max L A (x (1) , . . . , x (r) ),
Proof
Now, Lagrange's method implies that for any k ∈ [r] , there exists a µ k such that for every
Proof
Hence, for any s ∈ [n k ] , we find that
Proof
and therefore, ΣA
Proof
(c) Suppose that A is regular. If p = r, inequality (4) yields
Proof
Hence, equality holds in (24) for all k ∈ [r]. If p > r, Proposition 4, clause (c) implies that
Proof
and so equality holds in (24) for all k ∈ [r] , completing the proof of Theorem 21.
Proof
Bound (24) is quite efficient for some classes of nonnegative matrices, like (0, 1)-matrices; in particular, if a (0, 1)-matrix A has no zero slices, then (24) never worse than the similar bound of Friedland and Lim ([13] , Lemma 9.1):
Proof
and could be better than the more complicated version of Li [19] . However, bound (24) is ill-suited to matrices with small slice sums; e.g., if the slice sums are zero, then bound (24) is vacuous. Thus, we state another tight simple bound, whose proof is omitted:
Proposition 22
If A is a matrix and p > 1, then
Proposition 22
If all entries of A are zero except the entries of single fiber, then equality holds.
Proposition 22
Recall that if A is an m × n 2-matrix, then A 2 2 salsifies the following inequalities
Proposition 22
The purpose of the next theorem is to generalize these bounds to hypermatrices 5 . 
Theorem 23
Proof We give the proof of (24) Since A (G) is symmetric and nonnegative matrix η (r) (G) = ρ (A (G)); we set for short ρ (G) = ρ (A (G)) and call ρ (G) the spectral radius of G.
Theorem 23
A graph G is called k-partite if its vertices can be partitioned into k sets so that no edge has two vertices from the same set.
Theorem 23
Given a weighted r-graph G, and a vertex v ∈ V (G) , the sum d (v) := { ∑ G (e) : e ∈ E (G) and v ∈ e} is called the degree of v. A graph G is called regular if the degrees of its vertices are equal. An r-partite r-graph is called semiregular, if all vertices belonging to the same partition set have the same degree. A weighted r-partite graph is called rank-one if each vertex u can be assigned a real number x u such that G (i 1 , . . . , i r ) = x i 1 · · · x i r for every edge {i 1 , . . . , i r } ∈ E (G) .
Theorem 23
To the end of this section we list several new theorems about hypergraphs, which follow from the above results about hypermatrices. As mentioned before, other similar results can be found in [24] and its references. 
Equality holds if and only if G is a rank-one graph.
The proof of Theorem 21 can be adapted to yield the following lower bound on η (p) (G):
Equality holds if and only if G is a rank-one graph.
Theorem 26 Let p ≥ 1 and let G be a weighted r-partite r-graph. If n 1 , . . . , n r are the sizes of its partition sets, then, 
Equality holds if and only if G is a rank-one graph.
If p > 1 and equality holds in (27) , then G is semiregular. If p ≥ r, then equality holds in (27) if and only if G is semiregular. Theorem 23 implies an analog of Hofmeister's bound on the spectral radius of graphs and extends the main result of [22] , which is the case p = r. 
Concluding remark
It is well known that analytic methods can be applied to combinatorial problems. This paper may be regarded as a demonstration of the inverse application.

{'paper_id': '35118257', 'title': 'Combinatorial methods for the spectral p-norm of hypermatrices', 's2_url': 'https://api.semanticscholar.org/CorpusID:35118257', 'source': 'S2ORC'}