Spectral simplex method

Abstract

We develop an iterative optimization method for finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices. We consider matrix sets with product structure, i.e., all rows are chosen independently from given compact sets (row uncertainty sets). If all the uncertainty sets are finite or polyhedral, the algorithm finds the matrix with maximal/minimal spectral radius within a few iterations. It is proved that the algorithm avoids cycling and terminates within finite time. The proofs are based on spectral properties of rank-one corrections of nonnegative matrices. The practical efficiency is demonstrated in numerical examples and statistics in dimensions up to 500. Some generalizations to non-polyhedral uncertainty sets, including Euclidean balls, are derived. Finally, we consider applications to spectral graph theory, mathematical economics, dynamical systems, and difference equations.

1 Introduction

We address the problems of maximization and minimization of the spectral radius for nonnegative matrices. Such problems are notoriously hard because the spectral radius, as a function of matrix, is neither convex nor concave. Moreover, its Lipschitz continuity with respect to matrix coefficients is violated at matrices with multiple leading eigenvalues, which complicates the use of gradient and Newton’s methods. Nevertheless, for some matrix sets, the problem of optimizing the spectral radius can be efficiently solved. In this paper, we consider sets of nonnegative matrices with the product structure, or, in short, product families.

Definition 1

A family ${\mathcal {A}}$ of $d\times d$ matrices is called a product family if there are compact sets ${\mathcal {F}}_i \subset {\mathbb {R}}^d, \, i = 1, \ldots , d$, such that ${\mathcal {A}}$ consists of all possible matrices with $i$-th row from ${\mathcal {F}}_i$, for all $i = 1, \ldots , d$.

The sets ${\mathcal {F}}_i$ are called uncertainty sets. Thus, product families are sets of matrices with independent row uncertainties: their rows are independently chosen from the sets ${\mathcal {F}}_i$. Topologically, they are indeed products of the uncertainty sets: ${\mathcal {A}}= {\mathcal {F}}_1 \times \cdots \times {\mathcal {F}}_d$. Such families have been studied in the literature due to applications in spectral graph theory, asynchronous systems, mathematical economics, population dynamics, etc. (see [1, 4, 11, 16, 19, 24] and the references therein). In the sequel, if the converse is not stated, all rows from the uncertainty sets are assumed to be (entrywise) nonnegative. Thus, we consider nonnegative product families. In a recent paper [19] it was noted that such families admit effective methods for optimizing the spectral radius. One of them is the spectral simplex method, whose idea was suggested in the same work [19]. This method is applied when all uncertainty sets ${\mathcal {F}}_i$ are finite. It consists in consecutive increasing of the spectral radius by one-row corrections of a matrix. The main idea is the following. We take a matrix $A$ from a product family ${\mathcal {A}}$ and compute its Perron–Frobenius eigenvector ${\varvec{v}}$. Then, for each $i = 1, \ldots , d$, we try to maximize the scalar product of ${\varvec{v}}$ with rows from the uncertainty set ${\mathcal {F}}_i$. If for all $i$, the maxima are attained at the rows of $A$, then $A$ is the matrix with the maximal spectral radius in the family ${\mathcal {A}}$. Otherwise, we replace one row of $A$, say, the $i$th one, with the row from ${\mathcal {F}}_i$ maximizing the scalar product. We obtain a new matrix, repeat the same procedure, and so on.

The advantage of this method is that it is applicable for both maximizing and minimizing the spectral radius. However, a significant shortcoming is that it works only for strictly positive matrices. If some row from ${\mathcal {F}}_i$ have a zero entry, then the algorithm may cycle. Even if it does not cycle, the terminal matrix may not provide a solution. A natural idea is to make all matrices positive by slight perturbations of coefficients and then apply the algorithm to the perturbed matrices. However, in practice, this leads to numerical errors in computing the optimal spectral radius which are difficult to control. The reason is that in high dimensions, even a very small perturbation of coefficients may significantly change the spectral radius (see, for instance [23], for the corresponding analysis).

The aim of this paper is to extend the spectral simplex method for general nonnegative matrices and to study its properties. This is done in Sects. 3 and 4. To this end, we have to elaborate a new routine for the algorithm, separately for the problems of maximizing and of minimizing the spectral radius. In case of strictly positive matrices, both algorithms coincide with that described in [19]. Moreover, this extension allows us to apply the spectral simplex method for the case when the uncertainty sets ${\mathcal {F}}_i$ are not finite, but polyhedral, defined by systems of linear inequalities. Some problems studied in the literature can be reduced to optimizing the spectral radius for product families with polyhedral uncertainty sets, see [16] (the projection matrices in population dynamics) and [6] (matrices with fixed graph and row sums).

The practical efficiency of the algorithm is demonstrated in Sect. 5, in numerical examples with randomly generated matrices of dimensions from 5 to 500. For instance, in case when the dimension $d=50$ and each uncertainty set consists of two rows, the family ${\mathcal {A}}$ has the structure of the $50$-dimensional Boolean cube. The number of vertices $2^{50}$ of this cube makes the exhaustion of all matrices from ${\mathcal {A}}$ impossible. The spectral simplex method makes $29$ iterations and finds the matrix with the maximal spectral radius within $t = 0.6$ s. of computer time (in a standard laptop). In dimension $d=100$ when each uncertainty set consists of 50 rows, it makes 197 iterations and solves the problem within 25 s.

In Sect. 2, we prove necessary theoretical results on one-row corrections of nonnegative matrices, which are, probably, of some independent interest. Sections 3 and 4 present the spectral simplex methods for maximizing and for minimizing the spectral radius respectively, prove their non-cyclicity and finite convergence (Theorems 1–3). The cases of finite and of polyhedral uncertainty sets are considered. Section 5 shows the statistics of numerical results. In Sect. 6, we make further extension to general convex uncertainty sets, possibly non-polyhedral. In particular, if all of them are Euclidean balls, then the maximal spectral radius can be efficiently found (Theorem 5). Finally, in Sect. 7, we consider applications to several different areas: optimizing the spectral radius of a graph, constructing a productive economy in the Leontief model, stability of positive linear switching systems, and finite difference equations with nonnegative coefficients.

Throughout this paper we use the following notation. For a matrix $A$, we denote by ${\varvec{a}}_i$ its $i$th row. For two vector ${\varvec{x}}, {\varvec{y}}\in {\mathbb {R}}^d$, we write ${\varvec{x}}\ge {\varvec{y}}$ (${\varvec{x}}> {\varvec{y}}$) if the vector ${\varvec{x}}- {\varvec{y}}$ is nonnegative (respectively, strictly positive). The support of a nonnegative vector is the set of indices of its positive entries: $\mathrm{supp} \, {\varvec{x}}= \{i \ | \ x_i > 0\}$. We denote by $\mathrm{int}(\cdot )$, $\mathrm{co} (\cdot )$, and $\mathrm{span} (\cdot )$ the interior, the convex hull, and the linear span respectively, by $|M|$ the cardinality of a finite set $M$, by $(\cdot , \cdot )$ the standard scalar product in ${\mathbb {R}}^d$, by $\Vert \cdot \Vert$ the Euclidean norm, by $I$ the $d\times d$ identity matrix. We write ${\varvec{x}}\perp {\varvec{y}}$ if $({\varvec{x}}, {\varvec{y}}) = 0$; for a subset $V\subset {\mathbb {R}}^d$ let $V^{\perp } = \{\, {\varvec{y}}\in {\mathbb {R}}^d \ | \ \forall \ {\varvec{x}}\in V \ ({\varvec{x}}, {\varvec{y}}) = 0\, \}$ be its orthogonal complement. We use the abbreviation LP for linear programming.

2 The spectral simplex method. Statement of the problem

2.1 Definitions and notation

The spectral radius $\rho (A)$ of a matrix $A$ is the maximal modulus of its eigenvalues. By the Perron–Frobenius theorem, if $A \ge 0$, i.e., $A$ is (entrywise) nonnegative, then there is a nonnegative eigenvector ${\varvec{v}}$ such that $A{\varvec{v}}= \lambda {\varvec{v}}$ with $\lambda = \rho (A)$. This eigenvector is called leading, as well as the eigenvalue $\lambda$. The leading eigenvector is simple if it is a unique (up to multiplication by a positive constant) eigenvector corresponding to $\lambda$. Thus, the leading eigenvector is simple if and only if the leading eigenvalue has geometrical multiplicity one, i.e., $\mathrm{rank}(A - \lambda I) = d-1$

Let ${\mathcal {F}}_1, \ldots , {\mathcal {F}}_d$ be some sets of nonnegative $d$-dimensional row vectors. Each ${\mathcal {F}}_i$ is assumed to be either finite or polyhedral. The latter means that

$$\begin{aligned} {\mathcal {F}}_i=\Bigl \{{\varvec{x}}\in {\mathbb {R}}^d\ \Bigl |\ {\varvec{x}}\ge 0,({\varvec{c}}_{\,i, j}, {\varvec{x}}) \le \gamma _{i,j}, \quad j = 1, \ldots , m_i\Bigr \}, \end{aligned}$$

(1)

where ${\varvec{c}}_{i, j}\in {\mathbb {R}}^d$ are given vectors and $\gamma _{i,j}$ are numbers. For the sake of simplicity, we assume all these polyhedra to be bounded. For the product family ${\mathcal {A}}= {\mathcal {F}}_1\times \cdots \times {\mathcal {F}}_d$, we consider the problem of maximizing the spectral radius:

$$\begin{aligned} \left\{ \begin{array}{l} \rho (A) \rightarrow \max \\ A\in {\mathcal {A}}, \end{array}\right. \end{aligned}$$

(2)

and the problem of minimizing the spectral radius:

$$\begin{aligned} \left\{ \begin{array}{l} \rho (A)\rightarrow \min \\ A\in {\mathcal {A}}. \end{array}\right. \end{aligned}$$

(3)

In general, these two problems are totally different. Indeed, $\rho (A)$ is the maximum of modules of eigenvalues of $A$, and the problems of maximizing maximum and of minimizing maximum are not equivalent. Nevertheless, as we see in Sects. 3 and 4, the spectral simplex method allows us to solve these problems in a similar, although not the same, way.

2.2 The theoretical base of the spectral simplex method

The following simple assertion can be found, for instance, in [2]. It establishes lower and upper bounds for the spectral radius by means of an arbitrary nonnegative vector.

Lemma 1

Let a matrix $A$ and a nonzero vector ${\varvec{x}}$ be nonnegative, $\mu \ge 0$ be a number. If $A{\varvec{x}}\ge \mu {\varvec{x}}$, then $\rho (A) \ge \mu$. If ${\varvec{x}}> 0$ and $A{\varvec{x}}\le \mu {\varvec{x}}$, then $\rho (A) \le \mu$.

Proof

Iterating the inequality $A{\varvec{x}}\ge \mu {\varvec{x}}$, we get $A^k{\varvec{x}}\ge \mu ^k{\varvec{x}}$, and therefore $\Vert A^k\Vert \, \Vert {\varvec{x}}\Vert \, \ge \, \mu ^k \Vert {\varvec{x}}\Vert$. Thus, $\Vert A^k\Vert \ge \mu ^k$. Taking the power $1/k$ and the limit as $k \rightarrow \infty$, we conclude $\rho (A) \ge \mu$. If ${\varvec{x}}> 0$, then there is a constant $c = c({\varvec{x}})$ such that $\Vert B\Vert \le c\Vert B{\varvec{x}}\Vert$ for every nonnegative matrix $B$. Hence, $\Vert A^k\Vert \le c\Vert A^k{\varvec{x}}\Vert \le c \mu ^k\Vert {\varvec{x}}\Vert$. Taking the power $1/k$ and the limit as $k \rightarrow \infty$, we obtain $\rho (A) \le \mu$. $\square$

We are going to apply Lemma 1 to a leading eigenvector of a matrix as follows: if $A \ge 0$ is a matrix with a leading eigenvector ${\varvec{v}}$ and if, for some matrix $B$, we have $B{\varvec{v}}\ge A{\varvec{v}}$, then $\rho (B)\ge \rho (A)$. Indeed, if we write $\lambda = \rho (A)$, then $B{\varvec{v}}\ge A{\varvec{v}}= \lambda {\varvec{v}}$. Applying Lemma 1 to the matrix $B$ and to the vector ${\varvec{x}}= {\varvec{v}}$, we conclude that $\rho (B)\ge \lambda$.

Now we need to introduce one notation. Let ${\mathcal {A}}$ be a nonnegative product family. A matrix $A \in {\mathcal {A}}$ is said to be minimal in each row if it has a leading eigenvector ${\varvec{v}}\ge 0$ such that $({\varvec{a}}_i, {\varvec{v}}) = \min _{{\varvec{b}}_i \in {\mathcal {F}}_i}({\varvec{b}}_i , {\varvec{v}})$ for all $i = 1, \ldots , d$. It is maximal in each row if it has a leading eigenvector ${\varvec{v}}> 0$ such that $({\varvec{a}}_i, {\varvec{v}}) = \max _{{\varvec{b}}_i \in {\mathcal {F}}_i}({\varvec{b}}_i , {\varvec{v}}), \, i = 1, \ldots , d$.

Note that the minimality in each row is defined with respect to an arbitrary leading eigenvector ${\varvec{v}}\ge 0$, while the maximality needs a strictly positive ${\varvec{v}}$.

Proposition 1

Let ${\mathcal {A}}$ be a nonnegative product family. If a matrix $\bar{A} \in {\mathcal {A}}$ is maximal (minimal) in each row, then it has the maximal (respectively, minimal) spectral radius among all matrices from ${\mathcal {A}}$.

Proof

Let $\bar{A} \in {\mathcal {A}}$ be maximal in each row and $\bar{{\varvec{v}}} > 0$ be the corresponding leading eigenvector of $\bar{A}$. Denote $\lambda = \rho (\bar{A})$. For every $A \in {\mathcal {A}}$, we have $A \bar{{\varvec{v}}} \le \bar{A} \bar{{\varvec{v}}} = \lambda \bar{{\varvec{v}}}$, hence, by Lemma 1, $\rho (A)\le \lambda$. For a matrix minimal in each row, the proof is the same. $\square$

Thus, to maximize the spectral radius in a product family ${\mathcal {A}}$ one needs to find a matrix $\bar{A} \in {\mathcal {A}}$ maximal in each row. Such a matrix can be constructed step-by-step, by successive changes of rows, according to the following lemma.

Lemma 2

Let $A\ge 0$ be a matrix and ${\varvec{v}}$ be its leading eigenvector. Let a matrix $B\ge 0$ be obtained from $A$ by replacing the $j$th row ${\varvec{a}}_j$ with a row ${\varvec{b}}_j$. Then we have

• (a) if $({\varvec{b}}_j, {\varvec{v}})>({\varvec{a}}_j, {\varvec{v}})$, then $\rho (B) \ge \rho (A)$. If, in addition, $B > 0$, then $\rho (B) > \rho (A)$;

• (b) if $({\varvec{b}}_j, {\varvec{v}}) <({\varvec{a}}_j, {\varvec{v}})$, then $\rho (B) \le \rho (A)$. If, in addition, $B > 0$, then $\rho (B) < \rho (A)$;

Proof

We denote $\lambda = \rho (A)$, $s = ({\varvec{b}}_j, {\varvec{v}}) - ({\varvec{a}}_j, {\varvec{v}})$, and ${\varvec{u}}= B{\varvec{v}}$. Observe that ${\varvec{u}}= A{\varvec{v}}+ s {\varvec{e}}_j = \lambda {\varvec{v}}+ s {\varvec{e}}_j$, where ${\varvec{e}}_j$ is the $j$th canonical basis vector. Therefore,

$$\begin{aligned} B\, {\varvec{u}}= B \bigl ( \lambda {\varvec{v}}+ s {\varvec{e}}_j \bigr ) = \lambda {\varvec{u}}+ s \, B {\varvec{e}}_j. \end{aligned}$$

(4)

a) Since $A{\varvec{v}}= \lambda {\varvec{v}}$, we have $B{\varvec{v}}\ge \lambda {\varvec{v}}$, and, by Lemma 1, $\rho (B) \ge \lambda$. If $B > 0$, then (4) implies $B{\varvec{u}}> \lambda {\varvec{u}}$, because $B{\varvec{e}}_j > 0$ and $s > 0$. Hence $B{\varvec{u}}> \lambda ' {\varvec{u}}$ for some $\lambda ' > \lambda$. By Lemma 1, $\rho (B) \ge \lambda ' > \lambda$.

b) The main difficulty for this case is that the inequality $B{\varvec{v}}\le \lambda {\varvec{v}}$ does not in general imply $\rho (B) \le \lambda$. It does if the vector ${\varvec{v}}$ is strictly positive (Lemma 1), which, however, may not be true. That is why we consider the restriction of the vector ${\varvec{v}}$ to a special subspace where it is positive. Denote by ${\mathcal {I}}$ the support of ${\varvec{v}}$, by $V_{\,{\mathcal {I}}} = \{(x_1, \ldots , x_d) \in {\mathbb {R}}^d \ | \ \forall i \notin {\mathcal {I}}\ x_i = 0\}$ the corresponding coordinate subspace, by $\tilde{{\varvec{v}}}$ the vector ${\varvec{v}}$ restricted to ${\mathcal {I}}$, by $\tilde{A}$ the ${\mathcal {I}}\times {\mathcal {I}}$ submatrix of $A$ (i.e, the matrix $A$ restricted to ${\mathcal {V}}_{\, {\mathcal {I}}}$), by $\tilde{{\varvec{a}}}_i$ the $i$th row of $\tilde{A}$, and by $\tilde{{\varvec{b}}}_i$ the row ${\varvec{b}}_i \in {\mathcal {F}}_i$ restricted to ${\mathcal {I}}$.

Clearly, $\rho (\tilde{A}) \le \rho (A)$. On the other hand, $\tilde{A} \tilde{{\varvec{v}}} = \lambda \tilde{{\varvec{v}}}$, hence $\rho (\tilde{A}) \ge \lambda = \rho (A)$, and therefore, $\rho (\tilde{A}) = \rho (A)$. If $j \notin {\mathcal {I}}$, then $({\varvec{a}}_j, {\varvec{v}}) = 0$, which is incompatible with $({\varvec{b}}_j, {\varvec{v}}) < ({\varvec{a}}_j, {\varvec{v}})$. Consequently, $j \in {\mathcal {I}}$, and hence the matrix $\tilde{B}$ is obtained from $\tilde{A}$ by replacing the row $\tilde{{\varvec{a}}}_j$ with $\tilde{{\varvec{b}}}_j$ so that $(\tilde{{\varvec{b}}}_j, \tilde{\varvec{v}}) < (\tilde{{\varvec{a}}}_j, \tilde{{\varvec{v}}} )$. Since $\tilde{{\varvec{v}}} > 0$, we can now apply Lemma 1 and obtain $\rho (\tilde{B}) \le \rho (\tilde{A})$. Thus, on the subspace $V_{{\mathcal {I}}}$, the spectral radius of $B$ is smaller than or equal to the spectral radius of $A$. All other eigenvalues of $B$ are equal to the corresponding eigenvalues of $A$. Hence, $\rho (B) \le \rho (A)$. If $B > 0$, then (4) implies $B{\varvec{u}}< \lambda {\varvec{u}}$, because $B{\varvec{e}}_j > 0$ and $s > 0$. Hence ${\varvec{u}}> 0$ and $B{\varvec{u}}< \lambda ' {\varvec{u}}$ for some $\lambda ' < \lambda$. By Lemma 1, $\rho (B) \le \lambda ' < \lambda$. $\square$

2.3 The idea of the spectral simplex method

Starting with some matrix $A_1 \in {\mathcal {A}}$ we build a sequences of matrices $A_1, A_2, \ldots$ by the following rule: $A_{k+1}$ is obtained from $A_k$ by changing one of its lines ${\varvec{a}}_i^{(k)}$ so that $({\varvec{a}}_i^{(k+1)}, {\varvec{v}}_k) > ({\varvec{a}}_i^{(k)}, {\varvec{v}}_k)$, where ${\varvec{v}}_k$ is a leading eigenvector of $A_k$. By Lemma 2, the spectral radius is non-decreasing in this sequence. The process terminates, when none of rows can be replaced, i.e., when the final matrix $A_N$ is maximal in each row. By Proposition 1, the matrix $A_N$ has the maximal spectral radius in the family ${\mathcal {A}}$, provided ${\varvec{v}}_N > 0$.

In each step, the new row ${\varvec{a}}_i^{(k+1)}$ is chosen from ${\mathcal {F}}_i$ to maximize the scalar product $({\varvec{a}}_i^{(k+1)}, {\varvec{v}}_{k})$. If ${\mathcal {F}}_i$ is finite, then the point of maximum ${\varvec{a}}_i^{(k+1)}\in {\mathcal {F}}_i$ can be found by exhaustion. If ${\mathcal {F}}_i$ is a polyhedron, then we find ${\varvec{a}}_i^{(k+1)}$ among its vertices solving an LP problem by the (usual) simplex method. Thus, the spectral simplex method acts as a greedy algorithm at each iteration. Now we describe the formal procedure of the algorithm.

2.4 The algorithm

Initialization. Taking arbitrary ${\varvec{a}}_i \in {\mathcal {F}}_i, \ i = 1, \ldots , d$, we form a matrix $A_1 \in {\mathcal {A}}$ with rows ${\varvec{a}}_1, \ldots , {\varvec{a}}_d$. Take its leading eigenvector ${\varvec{v}}_1$.

Main loop. The $k$ th iteration. We have a matrix $A_{k} \in {\mathcal {A}}$ composed with rows ${\varvec{a}}_i^{(k)} \in {\mathcal {F}}_i, i = 1, \ldots , d$. Compute its leading eigenvector ${\varvec{v}}_{k}$ (if it is not unique, take any of them) and for $i = 1, \ldots d$, find a solution $\bar{{\varvec{b}}}_i \in {\mathcal {F}}_i$ of the following problem:

$$\begin{aligned} \left\{ \begin{array}{l} ({\varvec{b}}_i ,{\varvec{v}}_{k})\rightarrow \max \\ {\varvec{b}}_i \in {\mathcal {F}}_i \end{array}\right. \end{aligned}$$

(5)

If ${\mathcal {F}}_i$ is finite, then this problem can be solved by exhaustion; if ${\mathcal {F}}_i$ is polyhedral, then it is solved as an LP problem, and $\bar{{\varvec{b}}}_i$ is found among its vertices.

If $(\bar{{\varvec{b}}}_i, {\varvec{v}}_{k}) = ({\varvec{a}}_i^{(k)}, {\varvec{v}}_{k} )$ and $i \le d-1$, then we set $i = i+1$ and solve problem (5) for the next row. If $i = d$, then the algorithm terminates. In case ${\varvec{v}}_{k} > 0$, the matrix $A_{k}$ is maximal in each row, and by Proposition 1, $A_{k} = \max _{A \in {\mathcal {A}}}\, \rho (A)$, i.e., $A_{k}$ is a solution. If $(\bar{{\varvec{b}}}_i, {\varvec{v}}_{k}) > ({\varvec{a}}_i^{(k)}, {\varvec{v}}_{k} )$, then we set ${\varvec{a}}^{(k+1)}_i = \bar{{\varvec{b}}}_i$, ${\varvec{a}}_j^{(k+1)} = {\varvec{a}}_j^{(k)}$ for all $j\ne i$ and form the corresponding matrix $A_{k+1}$. Thus, $A_{k+1}$ is obtained from $A_k$ by replacing its $i$th row by $\bar{{\varvec{b}}}_i$. Then we start $(k+1)$st iteration.

End.

The spectral simplex method for minimization problem (3) is the same, replacing maximum by minimum in the problem (5) and omitting the positivity assumption ${\varvec{v}}_{k-1}>0$ in the termination of the algorithm.

2.5 The case of strictly positive matrices

Let ${\mathcal {A}}$ be a product family with uncertainty sets ${\mathcal {F}}_i \subset {\mathbb {R}}^d_+$ that are either finite or polyhedral (1). Consider the problem of maximizing the spectral radius. Lemma 2 ensures that in the spectral simplex method, the spectral radius $\rho (A_k)$ does not decrease in $k$. However, it may not grow for several iterations, in which case the algorithm may cycle (Example 1 below). Besides, if the algorithm terminates after some $N$th iteration, and the final leading eigenvector ${\varvec{v}}_{N}$ is not strictly positive, then the final matrix $A_{N}$ may not have the maximal spectral radius in the family ${\mathcal {A}}$, i.e., it does not give a solution (Example 2). Nevertheless, if all the sets ${\mathcal {F}}_i$ consist of strictly positive rows, then none of these problems occur. In this case, Lemma 2 yields that the spectral radius grows with iterations, and by the Perron–Frobenius theorem, each matrix $A \in {\mathcal {A}}$ has a simple leading eigenvector (so, there is no uncertainty in choosing ${\varvec{v}}_{k}$ at each iteration), which is, moreover, strictly positive.

Proposition 2

If all uncertainty sets ${\mathcal {F}}_i$ are strictly positive, then the spectral radius $\rho (A_k)$ strictly increases with iterations $k$ of the spectral simplex method. In particular, the algorithm does not cycle and terminates within finite time. The same is true for the minimization problem (3), in which case $\rho (A_k)$ strictly decreases in $k$.

Thus, if all rows in the sets ${\mathcal {F}}_i$ are strictly positive, then the spectral simplex method always finds a solution within finite time, for both maximization and minimization problems. The main issue of this paper is to adopt the method to general nonnegative rows, in particular, to sparse matrices. There are several difficult points on this way, we emphasize them in the next subsection.

2.6 Problems in case of sparse matrices

If some rows contain zeros, then the spectral simplex method may cycle as the following example demonstrates.

Example 1

We consider the family ${\mathcal {A}}$ of $3\times 3$ matrices with the following uncertainty sets

$$\begin{aligned} {\mathcal {F}}_1=\left\{ \left( \frac{1}{2},\, 1,\, \frac{1}{2}\right) ,\, \left( \frac{1}{2}, \, \frac{1}{2},\,1\right) \right\} , \quad {\mathcal {F}}_2=\Bigl \{\bigl (0,1,0\bigr )\Bigr \},\quad {\mathcal {F}}_2=\Bigl \{\bigl (0,0,1\bigr )\Bigr \}. \end{aligned}$$

Thus, ${\mathcal {A}}$ consists of two matrices:

$$\begin{aligned} A_1=\left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} 1 &{} \frac{1}{2}\\ 0 &{} 1 &{} 0\\ 0 &{} 0 &{} 1 \end{array}\right) ;\quad A_2=\left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} \frac{1}{2} &{} 1\\ 0 &{} 1 &{} 0\\ 0 &{} 0 &{} 1 \end{array}\right) \end{aligned}$$

(6)

Denote by ${\varvec{a}}_1^{(1)}$ and ${\varvec{a}}_1^{(2)}$ the elements of ${\mathcal {F}}_1$, i.e., the first rows of $A_1$ and $A_2$ respectively. We start the spectral simplex method with the matrix $A_1$ and take its leading eigenvector ${\varvec{v}}_1 = (1,0,1)^T$. Since $\bigl ({\varvec{a}}_1^{(1)}, {\varvec{v}}_1 \bigr ) = 1$ and $\bigl ({\varvec{a}}_1^{(2)}, {\varvec{v}}_1 \bigr ) = 3/2$, we change the first row from ${\varvec{a}}_1^{(1)}$ to ${\varvec{a}}_1^{(2)}$ passing to the matrix $A_2$. Then we take the leading eigenvector ${\varvec{v}}_2 = (1,1,0)^T$ of $A_2$. Since $\bigl ({\varvec{a}}_1^{(2)}, {\varvec{v}}_2 \bigr ) = 1$ and $\bigl ({\varvec{a}}_1^{(1)}, {\varvec{v}}_2 \bigr ) = 3/2$, we pass back to the matrix $A_1$ with the leading eigenvector ${\varvec{v}}_1$. Thus, the algorithm cycles with the period $(A_1A_2)$.

The second trouble is that, without the positivity assumption, the leading eigenvector ${\varvec{v}}_k$ may not be unique, in which case the matrix $A_k$ has a subspace (of dimension $\ge$2) of leading eigenvectors. This not only makes the computation of ${\varvec{v}}_k$ more difficult and less stable numerically, but also makes the whole algorithm unstable. Indeed, a small perturbation of the matrix $A_k$ may cause a significant change of the eigenvector ${\varvec{v}}_k$ at $k$th iteration, which, in turn, changes the choice of a row ${\varvec{a}}_i^{(k+1)}$ and influences all further iterations. For example, if $A_1$ is the identity matrix of size $2$, then we can choose ${\varvec{v}}_1 = (1, 0)^T$. However, if one adds a small $\varepsilon > 0$ to the entry $(A_{1})_{21}$, then we always have ${\varvec{v}}_1 = (0,1)^T$.

Finally, if the algorithm terminates with a matrix $A_N$, whose leading eigenvector have some zero entries, then $A_N$ does not necessarily provide a solution as shown below:

Example 2

Consider the family ${\mathcal {A}}$ of $2\times 2$ matrices with the following uncertainty sets

$$\begin{aligned} {\mathcal {F}}_1=\left\{ \bigl (1, \, 0\bigr ),\,\bigl (3,\, 0\bigr )\right\} ,\quad {\mathcal {F}}_2=\Bigl \{\bigl (0,\,2\bigr )\Bigr \}. \end{aligned}$$

Thus, ${\mathcal {A}}$ consists of two matrices:

$$\begin{aligned} A_1=\left( \begin{array}{c@{\quad }c} 1 &{} 0\\ 0 &{} 2 \end{array}\right) ;\quad A_2=\left( \begin{array}{c@{\quad }c} 3 &{} 0\\ 0 &{} 2 \end{array}\right) \end{aligned}$$

(7)

The spectral simplex method (for maximization problem) starting with the matrix $A_1$ terminates immediately with the same matrix, because $A_1$ is maximal in each row with respect to its simple leading eigenvector ${\varvec{v}}_1 = (0,1)^T$. However, $\rho (A_1) < \rho (A_2)$, and hence, $A_1$ is not a solution. The reason is that the leading eigenvector ${\varvec{v}}_1$ is not positive.

The question arises whether it is possible to modify the spectral simplex method for general nonnegative matrices in order to satisfy three requirements:

• (1) to avoid cycling, i.e., to guarantee the termination within finite time;

• (2) to have a simple leading eigenvector at each iteration;

• (3) to have a strictly positive leading eigenvector at the last iteration.

We treat the spectral simplex method separately for maximization problem (2) and for minimization problem (3). In each case, we consider two ways to define the uncertainty sets ${\mathcal {F}}_i$: as finite sets and as polyhedra given by linear inequalities (1). Thus, we have four cases. In Sects. 3 and 4, we show that in all these cases the answer is affirmative: the spectral simplex method can be modified to fulfill all the conditions above.

3 Maximizing the spectral radius

In this section, we elaborate the spectral simplex method that solves maximization problem (2) and satisfies requirements (1)–(3) for all nonnegative matrices: it does not cycle, gives a solution within finite time, and ensures simple leading eigenvectors at all iterations. To this end, it suffices to pass to an irreducible family (the definition is given below) and chose a staring matrix in a special way. The theoretical base is provided by Propositions 3 and 4 on one-row changes of nonnegative matrices, which are, probably, of some independent interest.

3.1 Two auxiliary facts

The following proposition ensures that if an iteration of the spectral simplex method does not change the spectral radius, then it keeps the simplicity of the leading eigenvector.

Proposition 3

Let a matrix $A \ge 0$ have a simple leading eigenvector ${\varvec{v}}$, a matrix $B\ge 0$ be obtained from $A$ by replacing its $j$th row ${\varvec{a}}_j$ by ${\varvec{b}}_j$. If $({\varvec{b}}_j, {\varvec{v}}) \ne ({\varvec{a}}_j, {\varvec{v}})$ and $\rho (B) = \rho (A)$, then $B$ also has a simple leading eigenvector.

Proof

Let $\lambda = \rho (A)$ and $\bar{{\varvec{a}}}_i, \bar{{\varvec{b}}}_i$ denote the $i$th rows of matrices $\bar{A} = \lambda I - A$ and $\bar{B} = \lambda I - B$ respectively. Since ${\varvec{v}}$ is a simple eigenvector of $A$, we have $\, \mathrm{rank} ( \bar{A}) = d-1$, i.e., the rows $\{\bar{{\varvec{a}}}_i\}_{i=1}^{d}$ span a $(d-1)$-dimensional subspace of ${\mathbb {R}}^d$. Since $\bar{A} {\varvec{v}}= 0$, this subspace coincides with ${\varvec{v}}^{\, \perp }$. Hence, the dimension of linear span of the $d-1$ rows $\{\bar{{\varvec{a}}}_i\}_{i \ne j}$ is at least $d-2$. By the assumption, $(\bar{{\varvec{b}}}_j , {\varvec{v}}) = ({\varvec{b}}_j - \lambda {\varvec{e}}_j, {\varvec{v}}) = ({\varvec{b}}_j , {\varvec{v}}) - \lambda v_j \ne ({\varvec{a}}_j , {\varvec{v}}) - \lambda v_j = 0$. Thus, ${(\bar{{\varvec{b}}}_j , {\varvec{v}}) \ne 0}$, and therefore $\bar{{\varvec{b}}}_j \notin {\varvec{v}}^{\, \perp }$. We see that the vector $\bar{{\varvec{b}}}_j$ cannot be spanned by the system $\{\bar{{\varvec{a}}}_i\}_{i \ne j}$, which lies within the subspace ${\varvec{v}}^{\, \perp }$. Consequently,

$$\begin{aligned} \mathrm{dim}\, \bigl (\mathrm{span}(\{\bar{{\varvec{a}}}_i\}_{i \ne j}\cup \{\bar{{\varvec{b}}}_j\}) \bigr )= \mathrm{dim}\, \bigl (\mathrm{span}(\{\bar{{\varvec{a}}}_i\}_{i \ne j})\bigr )+ 1\ge d-1. \end{aligned}$$

Thus, $\, \mathrm{rank} (\bar{B}) \ge d-1$ and so $\, \mathrm{rank} (\lambda I - B) \, \ge \, d-1$. On the other hand, $\lambda$ is the leading eigenvalue for $B$, hence its geometric multiplicity is one, and the corresponding leading eigenvector is simple. $\square$

Remark 1

Thus, if we replace one line of a nonnegative matrix not changing its leading eigenvalue but changing the scalar product with the leading eigenvector, then the leading eigenvector remains simple. This, however, does not hold for the simplicity of the leading eigenvalue: replacing one line under all these assumptions may make the leading eigenvalue multiple.

The next proposition shows that if an iteration of the spectral simplex method increases the spectral radius, then it makes the leading eigenvector simple. We establish a more general statement, for rank-one corrections of matrices. A matrix $B$ is called a rank-one correction of a matrix $A$ if $\mathrm{rank}(B-A) \le 1$. We use the same term for the process of correction (i.e., for adding of a rank-one matrix to the matrix $A$) and for the result of this process (the matrix $B$). Clearly, replacing one line of a matrix is a rank-one correction.

Proposition 4

Let a matrix $B \ge 0$ be a rank-one correction of a matrix $A\ge 0$ and $\rho (B) > \rho (A)$; then $B$ has a simple leading eigenvalue.

The proof is in “Appendix”.

3.2 Fundamental theorem

Theorem 1

For the spectral simplex method for maximization problem (2), the following hold: if the initial matrix $A_1$ has a simple leading eigenvector, then so have all subsequent matrices $A_k$ at all iterations $k \ge 1$, and the algorithm does not cycle.

Proof is by induction in the number of iteration $k$. If the matrix $A_k$ at $k$th iteration has a simple leading eigenvector ${\varvec{v}}_k$, then, in case $\rho (A_{k+1}) = \rho (A_{k})$, Proposition 3 implies that $A_{k+1}$ also has a simple leading eigenvector. Indeed, $A_{k+1}$ is obtained from $A_k$ by replacing some row ${\varvec{a}}_j^{(k)}$ of $A_k$ with a row ${\varvec{b}}_j \in {\mathcal {F}}_j$ such that $({\varvec{b}}_j, {\varvec{v}}_k) > ({\varvec{a}}_j^{(k)}, {\varvec{v}}_k )$. Thus, the matrices $A = A_k$ and $B = A_{k+1}$ satisfy the assumptions of Proposition 3. In case $\rho (A_{k+1}) > \rho (A_{k})$ we apply Proposition 4, since $A_{k+1}$ is a rank-one correction of $A_k$. So, the leading eigenvalue of $A_{k+1}$, and hence its leading eigenvector, is simple. Thus, the matrices at all iterations have simple leading eigenvectors.

Let ${\varvec{e}}\in {\mathbb {R}}^d$ be a row of ones and $E$ be a $d\times d$ matrix of ones. For a given $\varepsilon > 0$, consider an $\varepsilon$-perturbed problem $\rho (A_{\varepsilon }) \rightarrow \max , \, A_{\varepsilon } \in {\mathcal {A}}_{\varepsilon }$ for which the uncertainty sets are ${\mathcal {F}}_{i, \varepsilon } = \bigl \{ {\varvec{b}}_i + \varepsilon {\varvec{e}}\ \bigl | \ {\varvec{b}}_i \in {\mathcal {F}}_i \bigr \}, \, i = 1, \ldots , d$. If $\{A_k\}_{k\in {\mathbb {N}}}$ is a sequence of matrices obtained in the spectral simplex method, then for the corresponding $\varepsilon$-perturbed matrices $A_{k, \varepsilon } = A_k + \varepsilon E$, we have: if $A_{k+1}$ is obtained from $A_k$ by replacing its $j$th row ${\varvec{a}}_j^{(k)}$ with a row ${\varvec{a}}_j^{(k+1)}\in {\mathcal {F}}_j$ such that $({\varvec{a}}_j^{(k+1)},{\varvec{v}}_k) > ({\varvec{a}}_j^{(k)}, {\varvec{v}}_k )$, then $\bigl ({\varvec{a}}_j^{(k+1)} + \varepsilon \, {\varvec{e}}, \, {\varvec{v}}_{k, \varepsilon }\bigr ) \, > \, \bigl ({\varvec{a}}_j^{(k)} + \varepsilon \, {\varvec{e}}\, , \, {\varvec{v}}_{k, \varepsilon } \bigr )$, whenever $\varepsilon > 0$ is small enough. Indeed, if an eigenvalue has the geometrical multiplicity one, then the corresponding eigenvector is a continuous (and even smooth) function of matrix coefficients (see, for instance, [17]). Hence the simple leading eigenvector ${\varvec{v}}_k$ of $A_k$ continuously depends on entries of $A_k$, i.e., ${\varvec{v}}_{k, \varepsilon } \rightarrow {\varvec{v}}_k$ as $\varepsilon \rightarrow 0$. Since the perturbed matrices $A_{k , \varepsilon }$ are strictly positive, from item a) of Lemma 2 it follows that $\rho (A_{k+1 , \varepsilon }) > \rho (A_{k , \varepsilon })$ for all $k$. Thus, the spectral radii of the perturbed matrices $A_{k, \varepsilon }$ strictly increase in $k$. On the other hand, if the algorithm cycles, then $A_k = A_{k+m}$ for some $k, m$, and hence $\rho (A_{k, \varepsilon }) = \rho (A_{k+m, \varepsilon })$ which is a contradiction. $\square$

3.3 Irreducibility condition

Theorem 1 guarantees that the matrices at all iterations have simple leading eigenvectors, provided so does the initial matrix $A_1$. Hence, there is no uncertainty in choosing eigenvectors ${\varvec{v}}_k$ of matrices $A_k$ in each step, and the spectral simplex method does not cycle. Moreover, the uniqueness of the leading eigenvector implies that its computation is numerically stable with respect to small perturbations of matrices. It remains only to find an initial matrix $A_1$ with a simple leading eigenvector. This can be done using irreducibility of the starting matrix.

Definition 2

A nonnegative $d\times d$ matrix is reducible if it has a nontrivial invariant coordinate subspace, i.e., a subspace spanned by some vectors ${\varvec{e}}_i$ of the canonical basis. Otherwise, the matrix is called irreducible.

Reducibility of a matrix $A \ge 0$ means that there is a proper nonempty subset $\Lambda \subset \{1, \ldots , d\}$ such that for each $i \in \Lambda$ the support of the $i$th column (i.e., the set of indexes of its strictly positive components) of $A$ is contained in $\Lambda$. The following fact of the Perron–Frobenius theory is well-known (see, for instance, [10, chapter8]).

Lemma 3

An irreducible matrix has a simple leading eigenvalue.

Thus, to apply the spectral simplex method to arbitrary nonnegative uncertainty sets it suffices to choose the starting matrix $A_1$ irreducible. This is possible precisely when the family ${\mathcal {A}}$ is irreducible.

Definition 3

A family ${\mathcal {A}}$ of nonnegative $d\times d$ matrices is reducible if all matrices of ${\mathcal {A}}$ have a common nontrivial invariant coordinate subspace. If ${\mathcal {A}}$ is not reducible, it is called irreducible.

There are several equivalent definitions of irreducibility. Consider the graph $G$ of the family ${\mathcal {A}}$. This graph has $d$ vertices; there is an edge from a vertex $i$ to a vertex $j$ if there is a matrix $A \in {\mathcal {A}}$ such that $(A)_{ji} > 0$. A family ${\mathcal {A}}$ is irreducible if and only if its graph $G$ is strongly connected, i.e., for every pair of vertices $i, j$ there is a path from $i$ to $j$. If the set ${\mathcal {A}}$ is finite, then its reducibility is equivalent to the reducibility of one matrix $\sum _{A \in {\mathcal {A}}} A$. On the other hand, reducibility is equivalent to the existence of a suitable permutation of the basis of ${\mathbb {R}}^d$, after which all matrices from ${\mathcal {A}}$ have a block upper-triangular form with $r \ge 2$ diagonal blocks $A^{(j)}$ of fixed sizes $d^{(j)}, \, j = 1, \ldots , r$:

$$\begin{aligned} A=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} A^{(1)} &{} * &{} \ldots &{} * \\ 0 &{} A^{(2)}&{} * &{} \vdots \\ \vdots &{} {} &{} \ddots &{} * \\ 0 &{} \ldots &{} 0 &{} A^{(r)} \end{array} \right) , \end{aligned}$$

(8)

where for each $j = 1, \ldots , r$, the family ${\mathcal {A}}^{(j)}$ in the $j$th diagonal block is irreducible [10]. Clearly, if ${\mathcal {A}}$ is a product family, then each ${\mathcal {A}}^{(j)}$ is also a product family with uncertainty sets of rows of length $d^{(j)}$. Since $\rho (A) = \max \{\rho (A^{(1)}), \ldots , \rho (A^{(r)})\}$, we see that the problem of maximizing of the spectral radius for a reducible product family is equivalent to $r$ similar problems for irreducible families of smaller dimensions. This enables us to make the following assumption.

The irreducibility assumption. For the maximization problem ( 2 ) the family ${\mathcal {A}}$ is assumed to be irreducible.

This assumption is made without loss of generality, since the general case is always reduced to it. The irreducible block families ${\mathcal {A}}^{(j)}$ from (8) can be found by a simple combinatorial algorithm (see, for instance, [9]).

Lemma 4

Assume a matrix $A$ is from an irreducible product family ${\mathcal {A}}$, and ${\varvec{v}}$ is a leading eigenvector of $A$. If for each $j = 1, \ldots , d$, we have $({\varvec{a}}_j, {\varvec{v}}) = \max \nolimits _{b_j \in {\mathcal {F}}_j}({\varvec{b}}_j, {\varvec{v}})$, then ${\varvec{v}}$ is strictly positive.

Proof

Let ${\mathcal {I}}$ be the support of the vector ${\varvec{v}}$. For every $j \notin {\mathcal {I}}$, we have $({\varvec{a}}_j, {\varvec{v}}) = \lambda v_j = 0$, and hence $({\varvec{b}}_j, {\varvec{v}}) = 0$ for all ${\varvec{b}}_j \in {\mathcal {F}}_j$, because $({\varvec{b}}_j, {\varvec{v}}) \le ({\varvec{a}}_j, {\varvec{v}}) = 0$. Thus, for each matrix $B \in {\mathcal {A}}$ we have $(B{\varvec{v}})_j = 0$, whenever $j \notin {\mathcal {I}}$, which contradicts the irreducibility of ${\mathcal {A}}$. Consequently, the support ${\mathcal {I}}$ is full, and so ${\varvec{v}}> 0$. $\square$

Thus, without loss of generality we can impose the irreducibility assumption on the product family ${\mathcal {A}}$. By Lemma 4, this assumption guarantees that the final matrix $A_N$ of the spectral simplex method has a positive leading eigenvector, i.e., Condition (3) formulated at the end of Sect. 2 is satisfied. Conditions (1) (non-cycling) and (2) (simple leading eigenvectors at each iteration) are also satisfied, provided the starting matrix $A_1$ has a simple leading eigenvector. The latter is important as the following example demonstrates.

Example 3

Consider the uncertainty sets ${\mathcal {F}}_i, i = 1,2,3$, from Example 1 and add the row of ones ${\varvec{e}}= (1,1,1)$ to the sets ${\mathcal {F}}_2$ and ${\mathcal {F}}_3$. All the uncertainty sets became two-element, and so, ${\mathcal {A}}$ consists of $8$ matrices. Moreover, the family ${\mathcal {A}}$ is irreducible, since it contains a positive matrix. However, the spectral simplex method started with the matrix $A_1$ (formula 6) cycles as in Example 1, and the additional rows do not help. Theorem 1 is inapplicable, because the starting matrix has non-unique leading eigenvector.

This example shows that the irreducibility alone does not guarantee the proper work of the spectral simplex method, and the initialization with an irreducible matrix $A_1$ is needed.

3.4 The algorithm. Initialization of the spectral simplex method

If the uncertainty sets ${\mathcal {F}}_i$ are finite, then we define the matrix $A_1$ as follows:

$$\begin{aligned} {\varvec{a}}_i = \frac{1}{|{\mathcal {F}}_i|}\, \sum _{{\varvec{b}}_i \in {\mathcal {F}}_i} \, {\varvec{b}}_i,\quad i = 1, \ldots , d. \end{aligned}$$

Thus, the $i$th row of $A_1$ is the arithmetic mean of all elements of ${\mathcal {F}}_i$. If the family ${\mathcal {A}}$ is irreducible, then so is the matrix $A_1$. Hence, $A_1$ has a simple leading eigenvector (Lemma 3), and therefore the spectral simplex method does not cycle (Theorem 1).

So, to find the vertex of the matrix polytope $P = \mathrm{co}({\mathcal {A}})$ with the maximal spectral radius, we need to start from an interior point $A_1 \in \mathrm{int} (P)$ which is, actually, the center of mass of vertices of $P$. It may happen that the terminal matrix $A_N$ (with the biggest spectral radius) does not belong to ${\mathcal {A}}$, i.e., still has some rows from $A_1$, which are not elements of the sets ${\mathcal {F}}_i$ but their convex combinations. The answer (the maximum of the spectral radius) is the same for ${\mathcal {A}}$ and for $P$. However, the point of maximum, the matrix $A_N$, may not be a matrix from ${\mathcal {A}}$ but a convex combination of several matrices from ${\mathcal {A}}$. If we want to find a solution from the set ${\mathcal {A}}$, then we replace every row ${\varvec{a}}_i^{(N)}$ of $A_N$ which is not from ${\mathcal {F}}_i$ by a row ${\varvec{a}}_i \in {\mathcal {F}}_i$ with the largest scalar product $\bigl ({\varvec{a}}_i, {\varvec{v}}_N \bigr )$. Since ${\varvec{a}}_i^{(N)} \in \mathrm{co}({\mathcal {F}}_i)$, it follows that $\bigl ({\varvec{a}}_i, {\varvec{v}}_N \bigr ) \ge \bigl ({\varvec{a}}_i^{(N)}, {\varvec{v}}_N \bigr )$, and hence the new matrix (denote it by $A_N'$) satisfies $A_N'{\varvec{v}}_N \ge A_N {\varvec{v}}_N = \lambda _N {\varvec{v}}_N$. Invoking Lemma 1, we obtain $\rho (A_N') \ge \lambda _N$. On the other hand, $\lambda _N$ is the largest spectral radius of matrices from $P$. Therefore $\rho (A_N') = \lambda _N$, and $A_N' \in {\mathcal {A}}$ is the matrix of maximal spectral radius.

If the uncertainty sets ${\mathcal {F}}_i$ are polyhedra defined by linear inequalities ( 1 ), then we construct $A_1$ as follows. For fixed $i$ and for every $j = 1, \ldots , d$, solve the LP problem: $x_j \rightarrow \max , \, {\varvec{x}}\in {\mathcal {F}}_i$, where ${\varvec{x}}= (x_1, \ldots , x_d)$. Clearly, $x_j \ge 0$. Let ${\varvec{x}}^{(ij)}$ be a vertex of the polyhedron ${\mathcal {F}}_i$ that gives a solution. Then the $i$th row of $A_1$ is the arithmetic mean $\frac{1}{d} \sum {\varvec{x}}^{(ij)}$. Doing this for all $i=1, \ldots , d$ we define $A_1$. If ${\mathcal {A}}$ is irreducible, then so is the matrix $A_1$ (Lemma 3), and we can apply Theorem 1.

Remark 2

We see that in case of polyhedral uncertainty sets, an irreducible starting matrix $A_1$ is constructed by solving at most $d^2$ LP problems in dimension $d$. In practice, it can be obtained much faster. Let us briefly describe the algorithm. Take some $i \in \{1, \ldots , d\}$, set $k_i = 0, {\varvec{a}}_i = 0 \in {\mathbb {R}}^d$ and for $j =1, 2\ldots$, do the following. Solve the LP problem $x_j \rightarrow \max ,\ {\varvec{x}}\in {\mathcal {F}}_i$ and set $n_i := n_i + 1, {\varvec{a}}_i := {\varvec{a}}_i + {\varvec{x}}^{(ij)}$, $j := \min \{ s > j \, \ s \notin \mathrm{supp}\, ({\varvec{a}}_i)\}$. If $j \le d$, then we return to the LP problem. Otherwise, we set the $i$th row of $A_1$ to be $\frac{1}{n_i}\, {\varvec{a}}_i$. Thus, after each iteration, we add the vector ${\varvec{x}}^{(ij)}$ to ${\varvec{a}}_i$, find zero entry of ${\varvec{a}}_j$ with minimal index bigger than $j$ and set this index to be next $j$, and so on, until $j > d$, after which the $i$th row of $A_1$ is found. Doing this for all $i$ we construct the matrix $A_1$.

Note that if the algorithm does not cycle, then it terminates within finite time, because it runs over a finite number of states (vertices of polyhedra ${\mathcal {F}}_i$). Combining Theorem 1 and Lemma 4 we obtain

Theorem 2

If a product family ${\mathcal {A}}$ is irreducible and the spectral simplex method for maximization problem (2) starts with an irreducible matrix $A_1$, then it terminates at a matrix with the maximal spectral radius in a finite number of iterations.

Thus, the spectral simplex method for the maximization problem consists of two steps: 1) the initialization described above; 2) the formal procedure described in Sect. 2.4. By Theorem 2, the algorithm terminates within finite time and the final matrix provides a solution.

4 Minimizing the spectral radius

4.1 Statement of the problem

As we mentioned in Sect. 2, the problems of maximizing and of minimizing the spectral radius are totally different. In particular, the spectral simplex method presented in the previous section for maximization problem is not applicable to minimization one. In this case, as the following example demonstrates, neither irreducibility of the family ${\mathcal {A}}$ nor strict positivity of the initial matrix $A_1$ guarantees non-cycling.

Example 4

We consider the family ${\mathcal {A}}$ of $3\times 3$ matrices with the following uncertainty sets:

$$\begin{aligned} {\mathcal {F}}_1= & {} \left\{ \Bigl (\frac{1}{2}, \, 1, \,\frac{1}{2}\Bigr ),\, \Bigl (\frac{1}{2},\, \frac{1}{2},\, 1\Bigr ) \right\} ,\ {\mathcal {F}}_2= \Bigl \{\bigl (0,1,0\bigr ),\,\bigl (1,1,1 \bigr )\Bigr \},\\ {\mathcal {F}}_2= & {} \Bigl \{\bigl (0,0,1\bigr ),\,\bigl (1,1,1 \bigr )\Bigr \}. \end{aligned}$$

The spectral simplex method for minimizing the spectral radius produces the following chain of matrices:

$$\begin{aligned} \left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} 1 &{} \frac{1}{2}\\ 1 &{} 1 &{} 1\\ 1 &{} 1 &{} 1 \end{array} \right) \rightarrow \left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} 1 &{}\frac{1}{2}\\ 0 &{} 1 &{} 0\\ 1 &{} 1 &{} 1 \end{array} \right) \rightarrow \left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} 1 &{} \frac{1}{2}\\ 0 &{} 1 &{} 0\\ 0 &{} 0 &{} 1 \end{array}\right) \rightleftarrows \left( \begin{array}{c@{\quad }c@{\quad }c} \frac{1}{2} &{} \frac{1}{2} &{} 1\\ 0 &{} 1 &{} 0\\ 0 &{} 0 &{} 1 \end{array}\right) \end{aligned}$$

This chain has a cycle $(A_3A_4)$. The matrices $A_1$ and $A_2$ have simple leading eigenvectors, the other have multiple ones. For the matrix $A_3$, we take ${\varvec{v}}_3 = (2,1,0)^T$, and for $A_4$, we take ${\varvec{v}}_4 = (2,0,1)^T$.

Thus, for minimizing the spectral radius, the spectral simplex method has to be modified in a different way.

4.2 Auxiliary facts and observations

A leading eigenvector of a matrix $A$ is called minimal if it has the smallest by inclusion support, i.e., there is no leading eigenvector with a strictly smaller support. Since the set of all possible supports is finite, a minimal leading eigenvector always exists but may not be unique. For a nonempty subset ${\mathcal {I}}\subset \{1, \ldots , d\}$, we write $V_{{\mathcal {I}}}$ for the linear span of the basis vectors ${\varvec{e}}_i\, i \in {\mathcal {I}}$. For example, if ${\mathcal {I}}= \mathrm{supp} \, {\varvec{x}}$, then ${\varvec{x}}\in V_{{\mathcal {I}}}$.

Let ${\varvec{v}}$ be an arbitrary minimal leading eigenvector of $A$. Denote by ${\mathcal {I}}$ its support, $|{\mathcal {I}}| = n \le d$, and by $\tilde{A}$ the corresponding $n\times n$ submatrix of $A$. The matrix $\tilde{A}$ is formed by elements of $A$ on the intersections of columns and rows with indices from the sect ${\mathcal {I}}$. By $\tilde{{\varvec{v}}}$ we denote the restriction of the eigenvector ${\varvec{v}}$ to the matrix $\tilde{A}$; the restrictions of rows and columns of $A$ to the matrix $\tilde{A}$ are also marked with tilde. We begin with two simple observations:

Observation 1

The vector $\tilde{{\varvec{v}}}$ is a simple leading eigenvector for $\tilde{A}$.

Otherwise, if there is an eigenvector $\tilde{{\varvec{u}}}$ corresponding to the leading eigenvalue and not co-linear to $\tilde{{\varvec{v}}}$, then the vector $\tilde{{\varvec{v}}}-\bigl (\min \nolimits _{i\in {\mathcal {I}},\, \tilde{{\varvec{u}}}_i > 0} \frac{v_i}{u_i}\bigr )\tilde{{\varvec{u}}}$, being a leading eigenvector of $\tilde{A}$, has a smaller support. This contradicts to the minimality of ${\varvec{v}}$.

Observation 2

If $A$ is a matrix at some iteration of the spectral simplex method for minimization problem (3), and ${\varvec{v}}$ is chosen as the leading eigenvector, then the next iteration involves only rows from ${\mathcal {I}}= \mathrm{supp}\, {\varvec{v}}$, and the next matrix also has invariant subspace $V_{{\mathcal {I}}}$.

Indeed, for every $j\notin {\mathcal {I}}$ we have $({\varvec{a}}_j, {\varvec{v}}) = 0$, and the inequality $({\varvec{b}}_j, {\varvec{v}}) < ({\varvec{a}}_j, {\varvec{v}})$ is impossible.

4.3 Description of the spectral simplex method for minimization problem

We start with an arbitrary initial matrix $A_1$. Take an arbitrary minimal leading eigenvector ${\varvec{v}}_1$ of $A_1$ and denote by ${\mathcal {I}}$ its support. By Observation 1, $\tilde{{\varvec{v}}}$ is a simple leading eigenvector of $\tilde{A}_1$. Starting the spectral simplex method (described in Section 2) with the vector ${\varvec{v}}_1$, we involve only rows from ${\mathcal {I}}$ (Observation 2), and the next matrix $A_2$ also has invariant subspace $V_{{\mathcal {I}}}$. If $\rho (\tilde{A}_2) = \rho (\tilde{A}_1)$, then by Proposition 3, the matrix $\tilde{A}_2$ has a simple leading eigenvector $\tilde{{\varvec{v}}}_2$, which is extended by zeros to an eigenvector ${\varvec{v}}_2$ of $A_2$. We have $\rho (\tilde{A}_1) \le \rho (A_2) \le \rho (A_1) = \rho (\tilde{A}_1) = \rho (\tilde{A}_2)$. Therefore $\rho (\tilde{A}_2) = \rho (A_2)$, and hence ${\varvec{v}}_2$ is a leading eigenvector of $A_2$. The support of ${\varvec{v}}_2$ is contained in ${\mathcal {I}}$, but does not necessarily coincide with it. In particular, ${\varvec{v}}_2$ is not necessarily minimal. Nevertheless, restricting $A_2$ and ${\varvec{v}}_2$ to the subspace $V_{{\mathcal {I}}}$ we continue the algorithm for the matrix $\tilde{A}_2$ and for its leading eigenvector $\tilde{{\varvec{v}}}_2$. By the next iteration, we arrive at a matrix $A_3$ and show in the same way that if $\rho (\tilde{A}_3) = \rho (\tilde{A}_2)$, then $\tilde{A}_3$ has a simple leading eigenvector $\tilde{{\varvec{v}}}_3$, etc. Thus, until the algorithm reduces the value of the spectral radius, we always have simple leading eigenvectors and work, in fact, in the coordinate subspace $V_{{\mathcal {I}}}$. When the algorithm reduces the spectral radius of a matrix $\tilde{A}_k$, i.e., when $\rho (\tilde{A}_{k+1}) < \rho (\tilde{A}_k)$, we come back to $d\times d$ matrices, consider the matrix $A_{k+1}$, take an arbitrary minimal leading eigenvector ${\varvec{v}}_{k+1}$ of that matrix, and start the process all over again. The algorithm terminates when a current matrix $A_N$ is minimal in each row, or, equivalently, $\tilde{A}_N$ is minimal in each row. By Proposition 1, $A_N$ has the minimal spectral radius.

Thus, the spectral simplex method for minimization problem consists of several blocks, each contains several iterations.

4.4 The algorithm

We have a product family ${\mathcal {A}}$ with uncertainty sets ${\mathcal {F}}_1, \ldots , F_d$ that are either finite or polyhedral.

Initialization. We take an arbitrary initial matrix $A_1 \in {\mathcal {A}}$, take one of its minimal leading eigenvectors ${\varvec{v}}_1$ and go to the first block.

Main loop. The $j$ th block, ${j\ge 1}$, consists of iterations $k = k_j , \ldots , k_{j+1}-1$. First, at the iteration $k_j$, we have a matrix $A_{\, k_j}$ and take an arbitrary minimal leading eigenvector ${\varvec{v}}_{k_j}$ of this matrix. Let ${\mathcal {I}}= \mathrm{supp}\, {\varvec{v}}_{k_j} = \{i_1, \ldots , i_n\}$. At all iterations of the $j$th block, we deal with $n\times n$ submatrices $\tilde{A}_{k}$ corresponding to the coordinate subspace

$$\begin{aligned} V_{{\mathcal {I}}}=\{(x_1, \ldots , x_d) \in {\mathbb {R}}^d \ | \ \forall i \notin {\mathcal {I}}\ x_i = 0\}. \end{aligned}$$

By Observation 1, the initial matrix $\tilde{A}_{k_j}$ has a simple leading eigenvector.

The $k$ th iteration, $k = k_j , \ldots , k_{j+1}-1$. We have a matrix $A_k$, its $n\times n$ submatix $\tilde{A}_k$ that has a simple leading eigenvector $\tilde{{\varvec{v}}}_k$. Until $m \le n$, starting with $m=1$, we set $i = i_m$ and solve the problem

$$\begin{aligned} \left\{ \begin{array}{l} (\tilde{{\varvec{b}}}_{i} ,\tilde{{\varvec{v}}}_{k})\rightarrow \min \\ {\varvec{b}}_{i} \in {\mathcal {F}}_{i}, \end{array} \right. \end{aligned}$$

(9)

where $\tilde{{\varvec{b}}}_i$ is the restriction of the row ${\varvec{b}}_i \in {\mathcal {F}}_i$ to the coordinate subspace $V_{\,{\mathcal {I}}}$. If the set ${\mathcal {F}}_i$ is finite, then this problem is solved by exhaustion, if ${\mathcal {F}}_i$ is polyhedral, then it is solved as an LP problem, and the solution is taken among its vertices. Denote by $\alpha$ the value of this problem.

If $(\tilde{{\varvec{a}}}_i^{(k)}, \tilde{{\varvec{v}}}_{k} ) = \alpha$ and $m = n$, then the matrix $A_k$ is minimal in each row and by Proposition 1, it has the minimal spectral radius in the family ${\mathcal {A}}$. The algorithm terminates with the solution $A_k$.

If $(\tilde{{\varvec{a}}}_i^{(k)}, \tilde{{\varvec{v}}}_{k} ) = \alpha$ and $m \le n-1$, then we set $i = i_{m+1}$ and solve the problem (9).

If $(\tilde{{\varvec{a}}}_i^{(k)}, \tilde{{\varvec{v}}}_{k} ) > \alpha$, then we set ${\varvec{a}}^{(k+1)}_i$ equal to the solution ${\varvec{b}}_i$ of the problem (9), ${\varvec{a}}_p^{(k+1)} = {\varvec{a}}_p^{(k)}$ for all $p\ne i$ and form the corresponding matrix $A_{k+1}$. Thus $A_{k+1}$ is obtained from $A_{k}$ by replacing the $i$th row ${\varvec{a}}_i^{(k)}$ with ${\varvec{b}}_i$. By Observation 2, the matrix $A_{k+1}$ has the same invariant subspace $V_{{\mathcal {I}}}$. Denote by $\tilde{A}_{k+1}$ be the corresponding $n\times n$ submatrix.

If $\rho (\tilde{A}_{k+1}) = \rho (\tilde{A}_{k})$, then we stay in the subspace $V_{{\mathcal {I}}}$ and start the $(k+1)$st iteration of the $j$th block. By Proposition 3, the matrix $\tilde{A}_{k+1}$ also has a simple leading eigenvector.

If $\rho (\tilde{A}_{k+1}) < \rho (\tilde{A}_{k})$, then we set $k_{j+1} = k+1$, take the matrix $A_{k_{j+1}}$ and start the $(j+1)$st block.

End.

4.5 Termination within finite time

By Observations 1 and 2, the $j$th block of the spectral simplex method is performed on the subspace $V_{{\mathcal {I}}}$ for matrices $\tilde{A}_{k_j}, \ldots , \tilde{A}_{k_{j}+s}$ until $\rho (\tilde{A}_{k_{j}+s}) < \rho (\tilde{A}_{k_{j}+s-1})$ for some $s \in {\mathbb {N}}$. Then we set $k_{j+1} = k_j +s$ and pass to the $(j+1)$st block. Thus, at all iterations of the $j$th block, the matrices $\tilde{A}_{k}$ have the same spectral radius $\rho _j$ and, by Proposition 3, each of them has a simple leading eigenvector. All full matrices $A_{k}$ also have the same spectral radius equal to $\rho _j$.

Theorem 3

In the spectral simplex method for minimization problem (3), for each $j \ge 1$, all the matrices of $j$th block $\tilde{A}_{k_j}, \ldots , \tilde{A}_{k_{j+1}-1}$ have simple leading eigenvectors. The entire algorithm does not cycle and terminates within finite time with the minimal spectral radius.

Proof

Since ${\varvec{v}}_{k_j}$ is the minimal leading eigenvector of the matrix $A_{k_j}$, it follows that $\tilde{A}_{k_j}$ has a simple leading eigenvector (Observation 1). At further iterations of this block, the spectral radius of the matrices $\tilde{A}_{k}, \, k = k_{j}+1, \ldots , k_{j+1}-1$, stays the same and is equal to $\rho (A_{k_j})$. Proposition 3 implies that all these matrices have simple leading eigenvectors. Invoking now the same argument with positive $\varepsilon$-perturbations as in the proof of Theorem 1, we see that, inside this block, the spectral simplex method does not cycle, and therefore, performs a finite number $s$ of iterations, after which we have $\rho (\tilde{A}_{k_j+s}) < \rho (\tilde{A}_{k_j+s-1}) = \rho (\tilde{A}_{k_j}) = \rho (A_{k_j})$. Note that for all $i \notin {\mathcal {I}}$ the $i$th rows of matrices $A_{k_j+s}$ and $A_{k_j}$ coincide. Therefore, the passage from $A_{k_j}$ to $A_{k_j+s}$ reduces the spectral radius on the subspace $V_{{\mathcal {I}}}$ and keeps all other eigenvalues. Hence, the matrix $A_{k_j+s}$ has either smaller spectral radius than $A_{k_j}$, or equal spectral radius, but with a smaller total multiplicity of the leading eigenvalue. To a matrix $A$, we associate a pair $\Lambda (A) = (\lambda , r)$, where $\lambda = \rho (A)$ and $r$ is the total multiplicity of the eigenvalue $\lambda$. On the set of those pairs, we consider the lexicographic order: $\Lambda (A_1) > \Lambda (A_2)$ if and only if either $\lambda _1 > \lambda _2$ or $\lambda _1 = \lambda _2$ and $r_1 > r_2$. We proved that $\Lambda (A_{k_j+s}) < \Lambda (A_{k_j})$. The sequence $\Lambda (A_{k_j}), \, j = 1, 2, \ldots$ strictly decreases, hence, the algorithm performs finitely many blocks. As shown above, the number of iterations inside each block is finite. Hence, the algorithm terminates within finite time, which concludes the proof. $\square$

5 Numerical results

The spectral simplex method works surprisingly fast in all practical examples for both maximization and minimization problems. We present statistics of the number of iterations performed by the algorithm for randomly generated uncertainty sets. Table 1 presents the results of numerical experiments for positive sets ${\mathcal {F}}_i$, each contains $n$ rows of dimension $d$, $i = 1, \ldots , d$. For the sake of simplicity, we take all the sets ${\mathcal {F}}_i$ of equal cardinality. Each entry of any row from ${\mathcal {F}}_i$ is uniformly distributed on $[0,1]$. The rows of the table correspond to the dimensions $d = 5, \, 10, \, 50, \, 100, \, 500$; the columns correspond to the number of elements $n$ in each uncertainty set ${\mathcal {F}}_i$. The table shows the total number of iterations performed by the algorithm. For every pair $(d, n)$ we made 5 experiments and put the arithmetic mean of the number of iterations rounded to the closest integer.

Let us recall that each iteration consists in replacing of one row of a matrix and in computing of the leading eigenvector of the new matrix. The latter is the most expensive routine, because all other operations are mere computing scalar products and comparing numbers. Thus, the number of iterations is equal to the number of computations of the Perron–Frobenius eigenvectors for $d\times d$ matrices. All those eigenvectors are simple (Theorems 1 and 3).

Table 1 The number of iterations for maximizing the spectral radius of positive $d\times d$ matrices

Observe that in the case $n=2$ (the Boolean cube), the number of iterations is about a half of the dimension. So, almost half of the initial rows are already optimal, the others are (in average) replaced once. For $n=5$, each row (in average) is replaced once. The average number of changes for each row grows very slow: only for $n=100$ we have two changes for one row.

For $d=10, n=100$, the set ${\mathcal {A}}$ contains $100^{10} = 10^{20}$ matrices. However, only $23$ of them are visited by the algorithm, and within the time $t = 0.3$ s. in a standard laptop the optimal matrix is found. For $d=100, n=100$, the set ${\mathcal {A}}$ contains $100^{100} = 10^{200}$ matrices. The algorithm performs 213 of them and arrives at the solution within $t=40$ s.

For the minimization problem, the numerical results are more or less the same, and we do not demonstrate them here. The next Table 2 shows the results for the sparse matrices. Each row contains either one or two nonzero elements in randomly chosen positions, those elements have uniform distribution on $[0,1]$. We see that the number of iterations is bigger than for positive matrices, but not much. The ratio is between 3/2 and 2. For $d=50, n=50$, the algorithm performs 131 iterations and spends $t=13$ s.

Table 2 The number of iterations for minimizing the spectral radius of sparse $d\times d$ matrices

Table 3 presents the results for polyhedral sets ${\mathcal {F}}_i$, each given by system (1) of $m$ linear inequalities (acually, $m+d$, if we take into account the inequalities $x_j \ge 0, \, j = 1, \ldots , d$). Here the number of iterations is essentially bigger. This is natural, because the number of vertices of polyhedra ${\mathcal {F}}_i$ grows fast with $m$. The case $d=20, m= 100$ takes 540 iterations and $t = 44$ s. The case $d=50, n=50$ takes 3258 iterations and about 20 min of computer time.

Table 3 The number of iterations for maximizing the spectral radius of nonnegative $d\times d$ matrices

Table 4 shows the results for minimization problem for polyhedral uncertainty sets. We see that the numbers of iterations are similar to those for maximization problem in Table 3.

Table 4 The number of iterations for minimizing the spectral radius of nonnegative $d\times d$ matrices

Remark 3

To conclude, we see that in practical examples the spectral simplex method works very efficiently, even in relatively high dimensions. We do not have any satisfactory theoretical bound for the number of iterations. Moreover, we suspect that such bounds are actually exponential in the dimension $d$, and there may be “nasty” examples with the Boolean cube ($n=2$), when the algorithm performs about $2^{\,d}$ iterations, like in the Klee-Minty example in linear programming [22]. We hope, nevertheless, that such situation are rare in practice and that the spectral simplex method works efficiently in the vast majority of practical applications, as the (usual) simplex method in solving LP problems. We leave two open questions concerning the complexity of the problem. For the sake of simplicity, we consider the case of maximization problem for positive matrices when all the sets ${\mathcal {F}}_i$ are two-element (the Boolean cube, $n=2$), so ${\mathcal {A}}$ contains $2^{\,d}$ positive matrices.

Question 1. Is there a polynomial-time algorithm solving the problem ${\rho (A) \rightarrow \max ,}$ ${A \in {\mathcal {A}}}$, where ${\mathcal {A}}$ is a Boolean cube of positive rational matrices?

Question 2. What is the complexity of the spectral simplex method for the problem from Question 1?

6 Generalizations. Non-polyhedral uncertainty sets

If all ${\mathcal {F}}_i$ are arbitrary compact sets, not necessarily finite or polyhedral, then most of properties established in Sect. 2 remain true. A matrix $A$ has the maximal/minimal spectral radius in the family ${\mathcal {A}}$ if and only if it is maximal/minimal in each row. This is proved in Theorem 4 below. The maximal and minimal values of the spectral radius are attained at extreme points of the set $P = \mathrm{co}\, ({\mathcal {A}})$, i.e., at matrices composed with rows from extreme points of the sets $\mathrm{co}\, ({\mathcal {F}}_i)$ (Corollary 1). Therefore, the algorithms of spectral simplex method for both maximization (Sect. 3) and minimization (Sect. 4) problems are still applicable. Similarly to the case of finite or of polyhedral uncertainty sets, at each iteration, when we have a matrix $A_k \in {\mathcal {A}}$ and its leading eigenvector ${\varvec{v}}_k$, the algorithm chooses an extreme point ${\varvec{a}}_i$ of the set $\mathrm{co} ({\mathcal {F}}_i)$ to maximize the scalar product $({\varvec{a}}_i, {\varvec{v}}_k)$. Although, in this case, the algorithm finds only an approximate solution and does not necessarily terminate within finite time, since the set of extreme points is infinite. Nevertheless, in some cases of non-polyhedral uncertainty sets, the solutions, i.e., the matrices maximal/minimal in each row can be spotted by effective criteria. For instance, if all ${\mathcal {F}}_i$ are Euclidean balls, then the solution is unique and can be easily computed (Theorem 5).

6.1 General compact uncertainty sets

Theorem 4

Let ${\mathcal {F}}_1, \ldots , {\mathcal {F}}_d$ be arbitrary compact row uncertainty sets and ${\mathcal {A}}$ be the corresponding product family of matrices. Suppose ${\mathcal {A}}$ is irreducible; then

• (i) there is a matrix $A \in {\mathcal {A}}$ maximal in each row. If for some $i$, the set ${\mathcal {F}}_i$ is a polytope, then the $i$th row of $A$ can be chosen from the set of its vertices.

• (ii) If some matrix $A\in {\mathcal {A}}$ is maximal in each row with respect to its leading eigenvector ${\varvec{v}}$, then ${\varvec{v}}> 0$ and $\rho (A) = \max \nolimits _{B \in {\mathcal {A}}}\rho (B) = \max \nolimits _{B \in \mathrm{co}({\mathcal {A}})}\rho (B)$.

• (iii) Assertions (i) and (ii) are true for minimum instead of maximum. In this case the family ${\mathcal {A}}$ may be reducible and the assertion ${\varvec{v}}> 0$ is replaced everywhere by ${\varvec{v}}\ge 0$.

Proof

Assume first that all the sets ${\mathcal {F}}_i$ consist of strictly positive rows. By compactness, the maximal spectral radius is achieved at some matrix $A \in {\mathcal {A}}$. Since $A$ is positive, it has a simple positive leading eigenvector ${\varvec{v}}$. By Lemma 2, if for some $j$, we have $({\varvec{a}}_j, {\varvec{v}}) < \max \nolimits _{{\varvec{b}}_j \in {\mathcal {F}}_j}({\varvec{b}}_j, {\varvec{v}})$, then the row ${\varvec{a}}_j$ can be replaced with the increase of the spectral radius, which is a contradiction. Thus, $({\varvec{a}}_i, {\varvec{v}}) = \max \nolimits _{{\varvec{b}}_i \in {\mathcal {F}}_i}({\varvec{b}}_i, {\varvec{v}})$. Consider now an arbitrary irreducible product family ${\mathcal {A}}$. Its positive $\varepsilon$-perturbation ${\mathcal {A}}_{\varepsilon } = {\mathcal {A}}+ \varepsilon E$ has a matrix $A_{\varepsilon } \in {\mathcal {A}}_{\varepsilon }$ which is maximal in each row. Its normalized leading eigenvector ${\varvec{v}}_{\varepsilon }$ tends to a leading eigenvector ${\varvec{v}}$ (probably, not unique) of the matrix $A = \lim \nolimits _{\varepsilon \rightarrow 0}A_{\varepsilon }$ as $\varepsilon \rightarrow 0$. Hence, the matrix $A$ is maximal in each row with respect to ${\varvec{v}}$. Since $\max \nolimits _{{\varvec{b}}_i \in {\mathcal {F}}_i}({\varvec{b}}_i, {\varvec{v}}) = \max \nolimits _{{\varvec{b}}_i \in \mathrm{co}({\mathcal {F}}_i)}({\varvec{b}}_i, {\varvec{v}})$, we see that $A$ is maximal for the family $P = \mathrm{co}(A)$ as well. In particular, if some uncertainty set ${\mathcal {F}}_i$ is a polytope, we may replace it by the set of its vertices, and get the same matrix $A$. This completes the proof of (i). The proof of (ii) follows now from Lemma 4. The proof of (iii) is literally the same, replacing all maxima by minima, Lemmas 2 and 4 by Lemma 3. $\square$

Corollary 1

For any product family ${\mathcal {A}}$, both the maximal and minimal spectral radii are achieved at extreme points of $\, \mathrm{co}\, ({\mathcal {A}})$.

The proof is in “Appendix”. This corollary implies, in particular, that the answers to problems (2) and (3) are not changed if we replace all uncertainty sets ${\mathcal {F}}_i$ by their convex hulls $\mathrm{co} ({\mathcal {F}}_i)$. If particular, the case of polyhedral sets is equivalent to the case of finite sets.

6.2 All uncertainty sets are Euclidean balls

Let each uncertainty set ${\mathcal {F}}_i$ be a Euclidean ball of radius $r_i$ centered at a point ${\varvec{c}}_i \ge 0$, $\, i = 1, \ldots , d$. We do not make any assumption on the numbers $r_i$ and on the centers ${\varvec{c}}_i$ except for nonnegativity of all ${\varvec{c}}_i$. Thus, the family ${\mathcal {A}}= {\mathcal {A}}({\varvec{c}}, {\varvec{r}})$ consists of all matrices $A$ such that $\Vert {\varvec{a}}_i - {\varvec{c}}_i\Vert \le r_i, \ i = 1, \ldots , d$. Note that matrices of ${\mathcal {A}}$ are not necessarily nonnegative. The problem is to find the maximal spectral radius of matrices from ${\mathcal {A}}$. This problem can also be formulated as follows:

Maximize the spectral radius of a nonnegative matrix given approximately: the $i$ th row is given with a precision $r_i$ in the Euclidean norm, $i = 1, \ldots , d$.

To begin with, we note that the problem can be restricted to nonnegative matrices of the family ${\mathcal {A}}$. Indeed, if one replaces all entries of a matrix $A \in {\mathcal {A}}$ by their modules, then its spectral radius will not decrease and all the inequalities $\Vert {\varvec{a}}_i - {\varvec{c}}_i\Vert \le r_i$ remain valid (because ${\varvec{c}}_i \ge 0$), hence $A$ remains in ${\mathcal {A}}$.

Since each ball ${\mathcal {F}}_i$ possesses a nonempty interior, it contains a strictly positive point. Therefore, ${\mathcal {A}}$ is irreducible, and we can invoke Theorem 4: to maximize the spectral radius we need to find $\bar{A} \in {\mathcal {A}}$, for which $(\bar{{\varvec{a}}}_i, {\varvec{v}})= \max \nolimits _{{\varvec{a}}_i \in {\mathcal {F}}_i}\, ({\varvec{a}}_i, {\varvec{v}})\,$ for all $i=1, \ldots , d$, where $\, {\varvec{v}}> 0$ is the leading eigenvector of $\bar{A}$. Thus, the matrix $\bar{A}$ is maximal in each row, and we need to characterize such matrices in case of Euclidean balls ${\mathcal {F}}_i$.

Since ${\mathcal {F}}_i$ is a ball of radius $r_i$, the maximality in each row is equivalent to that $\, \bar{{\varvec{a}}}_i={\varvec{c}}_i+r_i {\varvec{v}},\, i = 1, \ldots , d$ (we normalize ${\varvec{v}}$ as $\Vert {\varvec{v}}\Vert = 1$). Let ${\varvec{r}}= (r_1, \ldots , r_d)^T$ and $C$ be the matrix with rows ${\varvec{c}}_1, \ldots , {\varvec{c}}_d$. We have $\bar{A}=C+{\varvec{r}}{\varvec{v}}^T$. Multiplying by ${\varvec{v}}$ from the right we obtain $\lambda {\varvec{v}}= \bar{A} {\varvec{v}}= C{\varvec{v}}+ {\varvec{r}}\, ({\varvec{v}}, {\varvec{v}}) = C {\varvec{v}}+ {\varvec{r}}$. Thus, $\lambda {\varvec{v}}=C {\varvec{v}}+ {\varvec{r}}$, and so

$$\begin{aligned} \Bigl (\lambda I-C\Bigr ) {\varvec{v}}={\varvec{r}}. \end{aligned}$$

(10)

Expressing ${\varvec{v}}$ and substituting it to the equality $\Vert {\varvec{v}}\Vert = 1$, we arrive at the equation $\ f(\lambda ) = 1$, where

$$\begin{aligned} f(\lambda )=\Bigl \Vert \ \bigl (\lambda \, I-C\bigr )^{-1}\, {\varvec{r}}\ \Bigr \Vert . \end{aligned}$$

(11)

Theorem 5

If all the uncertainty sets ${\mathcal {F}}_i$ are Euclidean balls, then the maximal spectral radius $\lambda$ of the family ${\mathcal {A}}$ is a unique solution of the equation $f(\lambda ) = 1$.

Proof

The only thing remains to prove is the existence and uniqueness of the solution. The function $\, f(\lambda )$ decreases monotonically on the interval $\lambda \in \bigl (\rho (C),+\infty \bigr )$, this is seen after the expansion into a power series: $(\lambda I-C)^{-1}{\varvec{r}}=\sum _{k=0}^{\infty } \lambda ^{-k-1} C^k\,{\varvec{r}}$. Since $f(\lambda ) \rightarrow +\infty$ as $\lambda \rightarrow \rho (C)$ and $f(\lambda )\rightarrow 0$ as $\lambda \rightarrow +\infty$, it follows that $f$ attains each positive value at one point. Hence the equation $f(\lambda ) = 1$ has a unique solution. $\square$

The equation $f(\lambda ) = 1$ can efficiently be solved in several ways. For instance, by bisection or by Newton’s method. Another approach is to take squares of both parts of Eq. (11) and come to an algebraic equation for $\lambda$ (a polynomial of degree $2d$, whose unique positive root is $\lambda$).

7 Applications

7.1 Optimizing the spectral radius of a graph

The spectral radius of a graph is the spectral radius of its adjacency matrix $A$. The problem of maximizing/mimimizing the spectral radius under some restrictions on the graph (connectedness, a given number of vertices and edges, a given largest degree of a vertex, etc.) attract much attention in the literature (see [3, 5, 8, 15, 20] and the references therein). Since adjacency matrices are nonnegative, one can apply the spectral simplex method, provided the set of graphs possesses a product structure, either by rows or by columns. We give two examples of such problems.

Problem 1. Let us have a set of vertices $V = \{g_1, \ldots , g_d\}$, and for any vertex $g_i$ a finite family of subsets ${\mathcal {V}}_i$ of the set $V$ be given. Maximize/minimize the spectral radius of a graph such that for every $i$ the set of incoming edges (more precisely, the set the corresponding adjacent vertices) for the vertex $g_i$ belongs to ${\mathcal {V}}_i$, $\, i = 1, \ldots , d$.

Problem 2. We are given a set of vertices $g_1, \ldots , g_d$ and a set of nonnegative integers $n_1, \ldots , n_d$. The problem is to find graphs with the largest and the smallest spectral radius among all directed graphs such that the number of incoming edges for any vertex $g_i$ is equal to $n_i$, $\, i = 1, \ldots , d$.

For the first problem all uncertainty sets ${\mathcal {F}}_i$ are finite, for the second one they are polyhedral and given by the systems of inequalities: ${\mathcal {F}}_i=\bigl \{x\in {\mathbb {R}}^d\ \bigl | \ \sum _{k=1}^d x_k \le n_i,\, 0\le x_k \le 1,\, k = 1, \ldots , d\, \bigr \}$. The minimal and maximal spectral radii are both attained at extreme points of the uncertainty sets (Corollary 1), i.e., precisely when the the $i$th row has $n_i$ ones and all other entries are zeros.

7.2 Leontief input–output model

The Leontief model in mathematical economics expresses inter-industry relationships in linear algebraic terms. Suppose the economy has $d$ sectors; the $i$th sector produces $x_i$ units of some single homogeneous good, and to produce one unit it consumes $a_{ij}$ units from sector $j$. In addition, each sector must leave $b_i$ units of its output to consumers (the final demand). Thus, for every $i=1, \ldots , d$ we have the following linear equality

$$\begin{aligned} x_i=b_i+\sum _{j=1}^{d}\, a_{\, i j}\, x_j, \end{aligned}$$

We write $A$ for the $d\times d$ matrix with coefficients $a_{ij}$ (the consumption matrix or input–output matrix), ${\varvec{x}}= (x_1, \ldots , x_d)$ for the vector of total output, and ${\varvec{b}}= (b_1, \ldots , b_d)$ for the vector of final demand. Thus, we have the following equation in matrix form

$$\begin{aligned} {\varvec{x}}=A\, {\varvec{x}}+{\varvec{b}}. \end{aligned}$$

(12)

The economy is productive if for every vector ${\varvec{b}}\ge 0$ this equation has a solution ${\varvec{x}}\ge 0$. In other words, the economy is able to provide any final demand. According to the Leontief theorem [12], the economy is productive if and only if $\rho (A) < 1$. Indeed, if $\lambda = \rho (A) \ge 1$, then Eq. (12) does not have a solution if ${\varvec{b}}= {\varvec{v}}$ is the leading eigenvector of $A$. Otherwise, we substitute ${\varvec{b}}= {\varvec{v}}$ into (12) and conclude that ${\varvec{x}}\ge {\varvec{v}}$. Hence, ${\varvec{x}}\ge A{\varvec{v}}+ {\varvec{v}}= (\lambda + 1){\varvec{v}}\ge 2{\varvec{v}}$. After $k$ steps we obtain ${\varvec{x}}\ge k {\varvec{v}}$, which becomes impossible as $k \rightarrow \infty$. On the other hand, if $\lambda < 1$, then the vector ${\varvec{x}}= \sum _{k=0}^{\infty }A^k \, {\varvec{b}}$ is a nonnegative solution of (12).

Assume now that for every $i$, we have several types of technologies to organize production in $i$th sector, each type has its own row of coefficients ${\varvec{a}}_i = (a_{i1}, \ldots , a_{id})$. Denote by ${\mathcal {F}}_i$ this set of rows ${\varvec{a}}_i$. The problem is to select a type of technology for each $i$ to obtain a productive economy. Thus, given uncertainty sets ${\mathcal {F}}_i, \, i = 1,\ldots , d$, we need to obtain a consumption matrix $A$ form the corresponding product family ${\mathcal {A}}$ such that $\rho (A) < 1$, or to prove its non-existence. This problem is solved by finding $\min _{A \in {\mathcal {A}}}\rho (A)$ using the spectral simplex method. Let us remark that here the ability of the spectral simplex method to work with sparse matrices becomes crucial, because the consumption matrices usually have many zero entries.

7.3 Positive linear switching systems

In general, our results cannot be extended directly to arbitrary matrices, without the nonnegativity assumption. However, for some classes of matrices this can be done. For instance, for the class of Metzler matrices. A matrix is called Metzler if all its off-diagonal elements are nonnegative. Thus, a matrix $A$ is Metzler if $\alpha I + A \ge 0$, whenever $\alpha > 0$ is large enough. A leading eigenvalue $\lambda$ of a Metzer matrix is its biggest real eigenvalue. If the matrix $\alpha I + A$ is nonnegative, then $\lambda + \alpha \ge 0$ is its leading (i.e., Perron–Frobenius) eigenvalue, with the same leading eigenvector. For product family of Metzler matrices, every uncertainty set ${\mathcal {F}}_i$ consists of rows nonnegative in all coordinates, except, maybe, for the $i$th one. The problem of maxiizing/minimizing the spectral radius becomes maximizing/minimizing the largest real eigenvalue. The spectral simplex method for both problems stays literally the same. In particular, Theorems 1–4 are true for Metzler matrices (replacing spectral radii by biggest real eigenvalues).

One of the main applications of Metzler matrices is stability of linear switching systems (LSS). For a given compact set of matrices ${\mathcal {A}}$, the LSS is a linear differential equation $\dot{x}(t) = A(t)x(t)$ with an initial condition $x(0) = x_0 \in {\mathbb {R}}^d$, where $A(t) \in {\mathcal {A}}$ for almost all $t$. An LSS is called stable if for any measurable function $A: {\mathbb {R}}_+ \rightarrow {\mathcal {A}}$ and for any $x_0$ we have $x(t) \rightarrow 0$ as $t \rightarrow +\infty$. There is an extensive literature on LSS stability (see the bibliography in [13, 14]). A necessary condition for stability is that all matrices from ${\mathcal {A}}$ are Hurwitz, i.e., all their eigenvalues have negative real parts. A sufficient condition is the existence of a convex Lyapunov function, i.e., positive homogeneous function on ${\mathbb {R}}^d$ (actually, a norm) $f(x)$ that decreases in $t$ along any trajectory $x(t)$ of the system. If $B = \{x \in {\mathbb {R}}^d \ | \ f(x)\le 1\}$ is a unit ball of that norm, then for every $x$ on the boundary of $B$ there is $\tau > 0$ such that $x + \tau Ax \in \mathrm{int} B$. This property characterizes Lyapunov functions. LSS is called positive if all matrices from ${\mathcal {A}}$ are Metzler. In this case any trajectory $x(t)$ starting in the positive orthant ${\mathbb {R}}^d_+$ stays in ${\mathbb {R}}^d_+$ for all $t \in [0, +\infty )$. We consider only irreducible LSS when the family ${\mathcal {A}}$ is irreducible. We are going to see that the problem of stability of positive LSS, being notoriously hard in general (see, for instance, [7]), has a simple solution if the family ${\mathcal {A}}$ has a product structure.

Theorem 6

Suppose a family of Metzler matrices ${\mathcal {A}}$ has a product structure; then the corresponding LSS is stable if and only if the biggest real eigenvalue of matrices from ${\mathcal {A}}$ is negative. In this case, the system has a Lyapunov function $f(x) = \max _{i} \frac{|x_i|}{v_i}$, where ${\varvec{v}}$ is the eigenvector corresponding to the biggest real eigenvalue.

Proof

If the biggest real eigenvalue is nonnegative, then the corresponding matrix is not Hutwitz, and hence, LSS is not stable. Conversely, if the biggest real eigenvalue $\lambda$ is negative and is attained for a matrix $\bar{A} \in {\mathcal {A}}$, then by Theorem 4, the corresponding eigenvector ${\varvec{v}}$ is positive, and $\bar{A}$ is maximal in each row. Therefore, for any $A \in {\mathcal {A}}$, we have $A {\varvec{v}}\le \bar{A}{\varvec{v}}= \lambda {\varvec{v}}< 0$. Hence, ${\varvec{v}}+ A {\varvec{v}}< {\varvec{v}}$ for all $A \in {\mathcal {A}}$, and therefore the convex set $B = \{{\varvec{x}}\in {\mathbb {R}}^d_+ \ | \ {\varvec{x}}\le {\varvec{v}}\}$ possesses the property of a unit ball of a Lyapunov function. The corresponding Lyapunov function is $f(x) = \max _{i} \frac{|x_i|}{v_i}$, and LSS is stable. $\square$

Thus, a positive LSS with the product structure always has a stationary “worst possible” trajectory that corresponds to the constant function $A(t)\equiv \bar{A}$, where $\bar{A} \in {\mathcal {A}}$ is the matrix with the biggest real eigenvalue. In case all uncertainty sets of ${\mathcal {A}}$ are finite or polyhedral, this matrix $\bar{A}$ can be found by the spectral simplex method, which solves the stability problem.

7.4 Difference equations with nonnegative coefficients

We consider a finite difference equation on the sequence $\{x_k\}_{k \in {\mathbb {Z}}}$:

$$\begin{aligned} x_{k}=\sum _{j=1}^{d} \, q_j\, x_{k-j},\quad k\ge d+1, \end{aligned}$$

(13)

where ${\varvec{q}}= (q_1, \ldots , q_d)$ is a given vector of coefficients. It is well-known that all solutions $\{x_k\}_{k \in {\mathbb {N}}}$ form an $d$-dimensional linear space, and any particular solution is uniquely defined by the initial conditions, i.e., by the values $x_1, \ldots , x_d$.

The largest possible rate of asymptotic growth of the sequence $\{x_k\}$ is $|\lambda |^k \, k^{\, \mu }\,$, where $\lambda$ is the maximal by modulo root of the characteristic polynomial $P_{{\varvec{q}}}(t) = t^{d} - \sum _{j=1}^{d} q_j \, t^{d-j}$ and $\mu$ is the multiplicity of that root (e.g. [18, 21]).

Now assume that the vector of coefficients ${\varvec{q}}$ is not fixed, and at any step $k$ of the recurrence we can chose independently any ${\varvec{q}}_k$ from a given uncertainty set ${\mathcal {Q}}\subset {\mathbb {R}}^d$. The question is what is the largest rate of asymptotic growth $\limsup _{k \rightarrow \infty }\, |x_k|^{\, 1/k}$ of the sequence $\{ x_k \}$? What strategy of choosing the vectors ${\varvec{q}}_k\in {\mathcal {Q}}$ provides the largest growth?

We treat the case, when all vectors from ${\mathcal {Q}}$ are nonnegative. In this case, as it was shown in [19, Proposition 1], the optimal strategy is always stationary. The largest growth is attained if we chose every time the same vector ${\varvec{q}}\in {\mathcal {Q}}$ for which the largest root $\lambda$ of the polynomial $P_{{\varvec{q}}}$ is maximal. This polynomial is actually the characteristic polynomial of the matrix of difference equation:

$$\begin{aligned} A=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} q_1 &{} q_2 &{} q_3 &{} \ldots &{} q_{d-1} &{} q_d\\ 1 &{} 0 &{} 0 &{} \ldots &{} 0 &{} 0\\ 0 &{} 1 &{} 0 &{} \ldots &{} 0 &{} 0\\ \vdots &{} \vdots &{} \vdots &{} {} &{} \vdots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \ldots &{} 1 &{} 0 \end{array}\right) , \end{aligned}$$

and hence, $\lambda$ is its Perron–Frobenius eigenvalue. When the vector ${\varvec{q}}$ runs over the set ${\mathcal {Q}}$, the matrix $A$ forms a product family ${\mathcal {A}}$ with the only nontrivial uncertainty set ${\mathcal {F}}_1 = {\mathcal {Q}}$, all other sets ${\mathcal {F}}_i$ are one-element. Thus, to find the largest rate of growth one needs to solve the problem $\rho (A) \rightarrow \max , \, A \in {\mathcal {A}}$. To apply the spectral simplex method we observe that if $q_d \ne 0$, then the matrix $A$ is irreducible. Hence, if we start the algorithm with the row ${\varvec{q}}^{(1)} \in {\mathcal {Q}}$ that has a nonzero last entry, then, by Theorem 1, the matrices at all iterations have simple leading eigenvectors and the algorithm does not cycle and finds a solution ${\varvec{q}}^{(N)} \in {\mathcal {Q}}$. Furthermore, the leading eigenvector of $A$ is ${\varvec{v}}= (\lambda ^{d-1}, \ldots , \lambda , 1)$, where $\lambda$ is the leading eigenvalue. Therefore, $({\varvec{a}}_1, {\varvec{v}}) = ({\varvec{q}}, {\varvec{v}}) = \sum _{j=1}^{d} q_j \, \lambda ^{d-j}$.

Changing variable $\tau = 1/\lambda$ and writing $S_{{\varvec{q}}}(\tau ) = \sum _{j=1}^{d} q_j \, \tau ^j$, we see that $({\varvec{a}}_1, {\varvec{v}}) = \lambda ^d S_{{\varvec{q}}}(\lambda )$ and the equation $P_{{\varvec{q}}}(\lambda ) = 0$ for the leading eigenvalue, becomes $S_{{\varvec{q}}}(1/\lambda ) = 1$. Thus, we come to the following problem

Problem. We are given a compact set ${\mathcal {Q}}\subset {\mathbb {R}}^d_+$. Find a vector ${\varvec{q}}\in {\mathcal {Q}}$ for which the root $\tau > 0$ of the equation $S_{{\varvec{q}}}(\tau ) = 1$ is minimal.

Solution. The spectral simplex method gives the following algorithm of solution. We start with arbitrary ${\varvec{q}}^{(1)} \in {\mathcal {Q}}$ that has a positive leading coefficient $q^{(1)}_d$ . At the $k$th iteration ($k \ge 1$), we have a vector ${\varvec{q}}^{(k)} \in {\mathcal {Q}}$. We solve the equation $S_{{\varvec{q}}^{(k)}}(\tau ) = 1$ and find $\max _{{\varvec{q}}\in {\mathcal {Q}}} S_{{\varvec{q}}}(\tau )$. If this is $1$, then ${\varvec{q}}^{(k)}$ is a solution, otherwise, if $\max _{{\varvec{q}}\in {\mathcal {Q}}} S_{{\varvec{q}}}(\tau ) > 1$, then we chose ${\varvec{q}}^{(k+1)} \in {\mathcal {Q}}$ as a point of maximum and start the $(k+1)$st iteration.

If the set ${\mathcal {Q}}$ is either finite or polyhedral, then, by Theorem 1, this algorithm terminates within finite time.

Appendix

Lemma 5

Let $A$ and $X$ be $d\times d$ matrices and $\mathrm{rank}(X) = 1$, then the coefficients of the characteristic polynomial of the matrix $A_s = A + s X, \ s \in {\mathbb {R}},$ are affine functions of $s$.

Proof

Consider the factorization $X = \varvec{a} \varvec{b}^T$, where $\varvec{a}, \varvec{b} \in {\mathbb {R}}^d$, and pass to a basis in ${\mathbb {R}}^d$ with the first basis vector $\varvec{a}$. In this basis, $X$ has only one nonzero row (the first one). Since the determinant of a matrix depends linearly on its first row, the characteristic polynomial $p(\tau ) = \mathrm{det} (\tau I - A - sX)$ depends linearly on $s$. $\square$

Proof of Proposition 4

Denote $\lambda _0 = \rho (A), \lambda _1 = \rho (B)$ and assume, to the contrary, that $\lambda _1$ has multiplicity $m \ge 2$. For an arbitrary $s \in [0,1]$, we consider the matrix $A_s = (1-s)A + sB$ and its characteristic polynomial $p_s(\tau ) = \mathrm{det}\, (\tau I - A_s)$. In particular, $p_0$ and $p_1$ are the characteristic polynomials of $A_0 = A$ and $A_1 = B$ respectively. By Lemma 5, we have

$$\begin{aligned} p_s=(1-s)\, p_0+s\, p_1. \end{aligned}$$

(14)

Since $\lambda _1$ is a root of multiplicity $m$ for the polynomial $p_1$, we have $p_1(\tau ) = (\tau - \lambda _1)^m q(\tau )$, where $q(\tau )$ is a polynomial with $q(\lambda _1)\ne 0$. If $m$ is even, then there is $\delta > 0$ such that $p_1(\tau ) \ge 0$ whenever $|\tau - \lambda _1| < \delta$. On the other hand, since $\lambda _1 > \lambda _0$ and $p_0 (\tau )$ is positive in the interval $(\lambda _0, +\infty )$, a small enough value of $\delta > 0$ guarantees that $p_0(\tau ) > \varepsilon > 0$ whenever $|\tau - \lambda _1| < \delta$. Hence, $p_s(\tau ) > 0$ at those $\tau$, for any $s \in (0,1)$. Since $A_s \ge 0$, its spectral radius $\rho (A_s)$ is the largest real root of the polynomial $p_s$. Therefore, $|\rho (A_s) - \lambda _1| \ge \delta$ for all $s \in (0,1)$, which contradicts the continuity of the spectral radius as $s$ tends to one, because $\rho (A_1) = \lambda _1$. Now, if $\lambda _1$ has an odd multiplicity $m \ge 3$, then the matrix $B$ is reducible as follows from the Perron–Frobenius theorem: there is a proper permutation of the canonical basis after which $B$ reduces to the following upper-triangular block form:

$$\begin{aligned} B=\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} B^{(1)} &{} * &{} \ldots &{} * \\ 0 &{} B^{(2)}&{} * &{} \vdots \\ \vdots &{} {} &{} \ddots &{} * \\ 0 &{} \ldots &{} 0 &{} B^{(r)} \end{array} \right) , \end{aligned}$$

(15)

where $r \ge m$, each matrix $B^{(i)}$ is irreducible, exactly $m$ of these matrices have simple leading eigenvalue $\lambda _1$, while the rest $(r-m)$ blocks having their leading eigenvalues smaller than $\lambda _1$ (see, for instance, [10, chapter8]). Let $i_1$ and $i_2$ ($i_1 < i_2$) be the two smallest indices for which $\rho (B^{(i_1)}) = \rho (B^{(i_2)}) = \lambda$.

The principal submatrix $B'$ of $B$ comprising the blocks $B^{(1)}, \ldots , B^{(i_2)}$ represents a rank-one correction of the submatrix $A'$ extracted from the same rows/columns of $A$ that constitute $B'$ in $B$, as far as $\mathrm{rank}\, (B' - A' ) \le \mathrm{rank}\, (B - A) \le 1.$ Since $\rho (A' ) \le \rho (A) < \lambda _1$, we get the rank-one correction $B'$ of matrix $A'$ that has the largest eigenvalue $\lambda _1 > \rho (A )$ of multiplicity $2$. This is impossible as has been proved above, for the case of oven multiplicity. $\square$

Proof of Corollary 1

If ${\mathcal {A}}$ is irreducible, then by Theorem 4, the maximal spectral radius is achieved at some matrix $A \in {\mathcal {A}}$ with a positive leading eigenvector ${\varvec{v}}$. For each $i$, the linear functional $f({\varvec{x}}) = ({\varvec{x}}, {\varvec{v}})$ on the set ${\mathcal {F}}_i$ attains its maximum at some extreme point ${\varvec{x}}= {\varvec{a}}_i'$ of the set ${\mathcal {F}}_i$. Let $A'$ be the matrix composed with rows ${\varvec{a}}_1', \ldots , {\varvec{a}}_d'$. Clearly, $A'$ is an extreme point of ${\mathcal {A}}$. Moreover, $A'{\varvec{v}}\ge A{\varvec{v}}$, and by Lemma 1, $\, \rho (A') \ge \rho (A)$, which by the maximality of $A$ implies that $\rho (A') = \max \limits _{B \in {\mathcal {A}}}\rho (B)$. If ${\mathcal {A}}$ is reducible, we make the permutation of the basis, after which all matrices from ${\mathcal {A}}$ get block upper triangular form. As we showed above, the irreducible block with the maximal spectral radius can be composed from rows which are extreme points of the corresponding uncertainty sets. Taking all other rows arbitrarily form the sets of extreme points of the corresponding uncertainty sets, we get a matrix $A'$ which is an extreme point of ${\mathcal {A}}$ and has the maximal spectral radius.

The proof for the minimal spectral radius is realized in the same way, but shorter: we do not assume irreducibility and omit the condition ${\varvec{v}}> 0$. $\square$