1 Introduction
For an unstructured perturbation, the largest singular values of certain matrices provide a clean and numerically tractable method for evaluating robust stability. There is a measure of stability similar to these largest singular values for a system that fails to be robustly stable using structured singular values [Reference Dahleh, Dahleh and Verghese1]. The structured singular value is a useful tool for analysing the robustness of stability and the performance of dynamical systems [Reference Doyle, Wall and Stein3].
The structured singular value was introduced by Doyle in [Reference Doyle2]. It is a matrix map
$\mu _{\mathbb {B}}: M_n(\mathbb {C})\longrightarrow [0,\infty )$
defined by
$$ \begin{align*}\mu_{\mathbb{B}}(M):= \begin{cases} 0 \quad&\mbox{if } \det(I+M\Delta)\neq 0 \mbox{ for all } \Delta\in \mathbb{B},\\ 1/\min_{\Delta\in \mathbb{B}}\{\|\Delta\|_2\;|\; \det(I+M\Delta)=0\} \quad &\mbox{otherwise.} \end{cases}\end{align*} $$
Here,
$M_n(\mathbb {C})$
denotes the set of all
$n\times n$
complex matrices,
$\mathbb {B}$
denotes the set of all diagonal blocks
$$ \begin{align*}\mathbb{B}:=\{\operatorname{diag}(\delta_1I_{k_1},\ldots,\delta_rI_{k_r},\Delta_1,\ldots,\Delta_s)\,|\;\delta_i \in \mathbb{C}, \Delta_j \in M_{n_i}(\mathbb{C})\} \subseteq M_n(\mathbb{C})\end{align*} $$
with
$\sum _{i=1}^rk_i+\sum _{j=1}^sn_j=n$
and
$\|A\|_2$
denotes the matrix
$2$
-norm of A (which is also equal to the largest singular value
$\sigma _{\max }(A)$
of A for
$A\in M_n(\mathbb {C})$
). Note that the complex perturbation block structure
$\mathbb {B}$
depends on the values of r (number of repeated scalar blocks), s (number of full blocks) and the
$k_i$
and
$n_i$
(dimensions of each block).
Some basic properties of the structured singular value can be deduced from the definition (see [Reference Doyle2]). For any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
:
-
(1)
$\mu _{\mathbb {B}}(\alpha M)=|\alpha | \mu _{\mathbb {B}}(M)$
for any
$M\in M_n(\mathbb {C})$
and
$\alpha \in \mathbb {C}$
; -
(2)
$\mu _{\mathbb {B}}(M)=\sigma _{\max }(M)$
for any
$M\in \mathbb {B}$
; -
(3)
$\rho (M)\leq \mu _{\mathbb {B}}(M)\leq \sigma _{\max }(M)$
for any
$M\in M_n(\mathbb {C})$
, where
$\rho (M)$
denotes the spectral radius (the magnitude of the largest eigenvalue) of M; -
(4) if we denote
$\mathcal {D}_{\mathbb {B}}:=\{\operatorname {diag}(d_1I_{k_1},\ldots ,d_rI_{k_r},d_{r+1}I_{n_1},\ldots ,d_{r+s}I_{n_s})\;|\;d_i\in (0,\infty )\}$
and
$\mathcal {U}_{\mathbb {B}}:=\{U\in \mathbb {B}\;|\; U \text { unitary}\}$
, then, for any
$M\in M_n(\mathbb {C})$
, (1.1)
$$ \begin{align} \max_{U\in \mathcal{U}_{\mathbb{B}}}\rho(MU)\leq \mu_{\mathbb{B}}(M)\leq \inf_{D\in\mathcal{D}_{\mathbb{B}} }\sigma_{\max}(DMD^{-1}). \end{align} $$
In fact, the first inequality in (1.1) is shown to be an equality in [Reference Doyle2]:
$$ \begin{align} \mu_{\mathbb{B}}(M)=\max_{U\in \mathcal{U}_{\mathbb{B}}}\rho(MU). \end{align} $$
Unfortunately, the optimisation problem in (1.2) is not convex. The lower function
$l(U):=\rho (MU)$
can have multiple local maxima which are not global and so the direct calculation of
$\max _{U\in \mathcal {U}_{\mathbb {B}}}\rho (MU)$
by gradient search might not find the actual maximum [Reference Packard and Doyle5]. In contrast, the function
$u(D):=\sigma _{\max }(DMD^{-1})$
does not have any local minima which are not global, so computing
$\inf _{D\in \mathcal {D}_{\mathbb {B}} }\sigma _{\max }(DMD^{-1})$
is a reasonable task [Reference Packard and Doyle5]. As shown in [Reference Packard and Doyle5], the equality
$\mu _{\mathbb {B}}(M) = \inf _{D\in \mathcal {D}_{\mathbb {B}} }\sigma _{\max }(DMD^{-1})$
always holds when
${2r+s\leq 3}$
. Conditions under which the structured singular value reaches the upper bound are given in [Reference Packard and Doyle5, Theorem 4.5] and a condition under which the structured singular value is equal to the spectral norm can be found in [Reference Packard and Doyle5, Theorem 4.4].
By using these results, Yamamoto and Kimura showed in [Reference Yamamoto and Kimura6] that
$\mu _{\mathbb {B}}(M)=\sigma _{\max }(M)$
when the matrix M is a square complex matrix satisfying
$SM=M^TS$
for some signature matrix S and the perturbation block structure
$\mathbb {B}$
has
$r=0$
or
$r=1,s=1$
(with some conditions). It is well known that if M is a normal matrix, then
$\rho (M)=\sigma _{\max }(M)$
and thus by property (3) above,
$\rho (M)=\mu _{\mathbb {B}}(M)=\sigma _{\max }(M)$
for any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
. Also, if M is a doubly stochastic matrix, then
$\rho (M)=\sigma _{\max }(A)=1$
(this fact does not necessarily hold for generalised doubly stochastic matrices) and again
$\mu _{\mathbb {B}}(M)=1$
for any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
. However, besides these three classes of matrices, to the best of our knowledge, there are no explicit structured singular values for other classes of matrices. Most of the literature related to computation is concerned with the approximation of the upper bound (see, for example, [Reference Guglielmi, Rehman and Kressner4] and the references therein).
We investigate a class of generalised row (column) stochastic matrices (square complex matrices having constant row (column) sum) appearing in (2.5). Matrices in this class need not be normal nor radial (a matrix having the spectral norm equal to the spectral radius). The explicit formula for the structured singular values of matrices in this class is given in terms of the constant row (or column) sum.
2 The results
Throughout, the block structure
$\mathbb {B}$
is a subset of
$M_n(\mathbb {C})$
having the form
$$ \begin{align*}\mathbb{B}:=\{\operatorname{diag}(\delta_1I_{k_1},\ldots,\delta_rI_{k_r},\Delta_1,\ldots,\Delta_s)\,|\;\delta_i\in \mathbb{C}, \Delta_j\in M_{n_i}(\mathbb{C})\}\end{align*} $$
for some
$r,s\in \mathbb {N}_0$
(the set of all nonnegative integers). Let A be an
$n\times n$
generalised row stochastic matrix, meaning that there exists
$c\in \mathbb {C}$
such that
$$ \begin{align} \sum_{j=1}^n A_{ij}=c\quad \mbox{for }~i=1,\ldots,n, \end{align} $$
and denote the largest singular values of A by
$\sigma $
, so that
$\sigma _{\max }(A)=\sigma =\| A \|_2$
.
Proposition 2.1. Let
$A\in M_n(\mathbb {C})$
be a generalised row stochastic matrix with the constant row sum
$c\in \mathbb {C}$
. Suppose that
$\|A\|_2=\sigma $
.
-
(1) Then
$|c|\leq \sigma $
. -
(2) If
$|c|=\sigma $
, then A must have the constant column sum c, that is, A is a c-generalised doubly stochastic matrix. -
(3) If
$|c|=\sigma $
, then
$\mu _{\mathbb {B}}(A^m)=\sigma ^m$
for all
$m\in \mathbb {N}$
and any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
.
Proof. Let
$\vec {1}\in \mathbb {C}^n$
be the vector all of whose components are one. By (2.1),
$A\vec {1}=c\vec {1}$
. By using the standard 2-norm
$\|\cdot \|$
on
$\mathbb {C}^n$
and the Cauchy–Schwarz inequality,
$$ \begin{align} |c|^2\|\vec{1}\|^2=\langle c\vec{1},c\vec{1} \rangle= \langle c\vec{1},A\vec{1} \rangle = \langle cA^* \vec{1},\vec{1} \rangle=|\langle cA^* \vec{1},\vec{1} \rangle | \leq \|cA^*\vec{1}\|\,\|\vec{1}\|, \end{align} $$
where
$A^*$
is the conjugate transpose of A. For any
$M\in M_n(\mathbb {C})$
and any nonzero vector
$y\in \mathbb {C}^n$
,
$$ \begin{align*}\|M\|_2:=\sup_{x\in (\mathbb{C}^*)^n}\frac{\|Mx\|}{\|x\|}\geq \frac{\|My\|}{\|y\|}.\end{align*} $$
Thus,
$\|cA^*\vec {1}\|\leq \|cA^*\|_2\|\vec {1}\|=|c|\,\|A^*\|_2\|\vec {1}\|$
. Since
$\|A^*\|_2=\|A\|_2$
for any
$A\in M_n(\mathbb {C})$
, (2.2) becomes
$$ \begin{align} |c|^2\|\vec{1}\|^2\leq \langle c A^* \vec{1},\vec{1} \rangle \leq |c|\,\|A\|_2\|\vec{1}\|^2=\sigma|c|\,\|\vec{1}\|^2. \end{align} $$
By (2.3), if
$c\neq 0$
, then
$\sigma \geq |c|$
. Since
$\sigma $
is always a nonnegative real number, if
$c=0$
, then
$\sigma \geq 0=|c|$
. Hence, the statement (1) holds.
If
$0=|c|=\sigma :=\|A\|_2$
, then
$A=O$
(the zero matrix) and thus the statement (2) is obviously true. Suppose that
$0\neq |c|=\sigma $
. Then the inequality (2.3) and hence the Cauchy–Schwarz inequality become equalities. This happens when
$cA^*\vec {1}=d'\vec {1}$
for some
$d'\in \mathbb {C}$
, that is,
$A^T\vec {1}=d\vec {1}$
, where
$d:=\bar {d'}/\bar {c}\in \mathbb {C}$
, giving the constant column sums
$$ \begin{align*}\sum_{i=1}^n A_{ij}=d\quad \mbox{for } j=1,\ldots,n.\end{align*} $$
By (2.3) with equality,
$$ \begin{align*}d'\|\vec{1}\|^2=\langle d'\vec{1},1\rangle=\langle c A^* \vec{1},\vec{1} \rangle = |c|\sigma\|\vec{1}\|^2,\end{align*} $$
which means that
$d'=|c|\sigma =|c|^2=c\bar {c}$
and
$d =\bar {d'}/\bar {c} = c$
. Hence, (2) holds.
To prove (3), for the case
$|c|=\sigma =\|A\|_2$
, we write
$c=\sigma e^{i\theta }$
for some
$\theta \in \mathbb {R}$
. Then
$$ \begin{align*}A\vec{1}=c\vec{1}=\sigma e^{i\theta} \vec{1},\end{align*} $$
so that
$\sigma e^{i\theta }$
is an eigenvalue of A. Now,
$$ \begin{align*}\sigma=|\sigma e^{i\theta}|\leq \rho(A)\leq \|A\|_2=\sigma\end{align*} $$
and hence
$\rho (A)=\sigma $
. For each
$m\in \mathbb {N}$
,
$\rho (A^m)=(\rho (A))^m$
and
$\|A^m\|_2\leq \|A\|_2^m$
because
$\|\cdot \|_2$
is a sub-multiplicative norm. By using the fact that
$\rho (M)\leq \mu _{\mathbb {B}}(M)\leq \|M\|_2$
for any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
and matrix
$M\in M_n(\mathbb {C})$
,
$$ \begin{align*}\sigma^m=(\rho(A))^m= \rho(A^m)\leq \mu_{\mathbb{B}}(A^m)\leq \|A^m\|_2\leq\|A\|_2^m=\sigma^m\end{align*} $$
for each natural number m, which proves (3).
The next result is a consequence of Proposition 2.1(3).
Corollary 2.2. Let
$D_1,D_2,\ldots ,D_k$
be doubly stochastic matrices of size
$n\times n$
and
$\delta _1,\delta _2,\ldots ,\delta _k$
be positive real numbers. Let
$$ \begin{align*}S_k(D):=\delta_1D_1+\delta_2D_2+\cdots+\delta_kD_k.\end{align*} $$
Then, for each
$m\in \mathbb {N}$
and any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
,
$$ \begin{align*}\mu_{\mathbb{B}}(S_k(D)^m)=(\delta_1+\delta_2+\cdots+\delta_k)^m.\end{align*} $$
Proof. Note that
$S_k(D)$
is a
$\delta $
-generalised doubly stochastic matrix with constant row sum
$\delta :=\delta _1+\delta _2+\cdots +\delta _k$
. Since
$S_k(D)\vec {1}=\delta \vec {1}$
, we have
$\rho (S_k(D))\geq \delta $
. Also,
$\|D_i\|_2=1$
for each
$i=1,\ldots ,k$
. By the triangle inequality for the spectral norm
$\|\cdot \|_2$
,
$$ \begin{align*}\delta\leq\rho(S_k(D))\leq\|S_k(D)\|_2=\|\delta_1D_1+\delta_2D_2+\cdots+\delta_kD_k\|_2\leq \sum_{i=1}^k\delta_i\|D_i\|_2=\delta.\end{align*} $$
Hence,
$\|S_k(D)\|_2=\delta $
and thus the result follows from Proposition 2.1(3).
It is still possible to calculate the structured singular value if the constant condition on the row sum in the proposition is slightly relaxed.
Corollary 2.3. Let
$A\in M_n(\mathbb {C})$
be a matrix such that
$\|A\|_2=\sigma $
. Let
$r_i:=\sum _{k=1}^n A_{ik}$
be the ith row sum for each
$i=1,\ldots ,n$
and
$c_j:=\sum _{k=1}^n A_{kj}$
be the jth column sum for each
$j=1,\ldots ,n$
. If
$|r_1|=\cdots =|r_n|=\sigma $
or
$|c_1|=\cdots =|c_n|=\sigma $
, then
$$ \begin{align*}\mu_{\mathbb{B}}(A^m)=\sigma^m\end{align*} $$
for each
$m\in \mathbb {N}$
and any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
containing, respectively,
$$ \begin{align*}\operatorname{diag}(e^{i\theta_1},e^{i\theta_2},\ldots,e^{i\theta_n}) \quad\text{or}\quad \operatorname{diag}(e^{i\gamma_1},e^{i\gamma_2},\ldots,e^{i\gamma_n}),\end{align*} $$
where
$r_j:=\sigma e^{i\theta _j}$
and
$c_j:=\sigma e^{i\gamma _j}$
for each
$j=1,\ldots ,n$
.
Proof. Note that
$\rho (M^*)=\rho (M)=\rho (M^T)$
and
$\rho (MN)=\rho (NM)$
for
$M,N\in M_n(\mathbb {C})$
. Also, by (1.2),
$\mu _{\mathbb {B}}(M)=\max _{U\in \mathcal {U}_{\mathbb {B}}}\rho (UM)$
. So, for
$U\in \mathcal {U}_{\mathbb {B}}$
,
$$ \begin{align} \mu_{\mathbb{B}}(M^T)=\mu_{\mathbb{B}}(M)=\mu_{\mathbb{B}}(UM)=\mu_{\mathbb{B}}(MU). \end{align} $$
If
$|r_1|=\cdots =|r_n|=\sigma $
and
$r_j=\sigma e^{i\theta _j}$
, where
$\theta _j\in \mathbb {R}$
for each
$j=1,\ldots , n$
, then
$A=UA_0$
, where
$U=\operatorname {diag}(e^{i\theta _1},e^{i\theta _2},\ldots ,e^{i\theta _n})$
and
$A_0$
is a generalised row stochastic matrix with the constant row sum
$\sigma \in \mathbb {C}$
. By the condition on the perturbation block structure
$\mathbb {B}$
, we conclude that
$A_0=U^* A$
with
$U^*\in \mathcal {U}_{\mathbb {B}}$
. Hence, by (2.4),
$\mu _{\mathbb {B}}(A_0)=\mu _{\mathbb {B}}(A)$
and the result follows from Proposition 2.1(3).
If
$|c_1|=\cdots =|c_n|=\sigma $
and
$c_j=\sigma e^{i\gamma _j}$
, where
$\gamma _j\in \mathbb {R}$
for each
$j=1,\ldots , n$
, then
$A^T=WB_0$
, where
$W=\operatorname {diag}(e^{i\gamma _1},e^{i\gamma _2},\ldots ,e^{i\gamma _n})$
and
$B_0$
is a generalised row stochastic matrix with the constant row sum
$\sigma \in \mathbb {C}$
. Then
$B_0=W^* A^T$
and
$W^*\in \mathcal {U}_{\mathbb {B}}$
, by the assumption of
$\mathbb {B}$
. Hence, by (2.4),
$\mu _{\mathbb {B}}(B_0)=\mu _{\mathbb {B}}(A)$
and again the result follows from Proposition 2.1(3).
Note that when
$r=0$
or
$k_1=k_2=\cdots =k_r=1$
, the assumption on the perturbation block structure
$\mathbb {B}$
in Corollary 2.3 will always be fulfilled. Furthermore, any matrix satisfying the assumptions of Corollary 2.3 must have the following property.
Proposition 2.4. Let
$A\in M_n(\mathbb {C})$
be a matrix such that
$\|A\|_2=\sigma $
. Let
$r_i:=\sum _{k=1}^n A_{ik}$
be the ith row sum for each
$i=1,\ldots ,n$
and
$c_j:=\sum _{k=1}^n A_{kj}$
be the jth column sum for each
$j=1,\ldots ,n$
.
-
(1) The row sums satisfy
$|r_1|=\cdots =|r_n|=\sigma $
if and only if
$A=\sigma W_\theta D$
, where
$W_\theta :=\operatorname {diag}(e^{i\theta _1},e^{i\theta _2},\ldots ,e^{i\theta _n})$
,
$r_k:=\sigma e^{i\theta _k}$
, for each
$k=1,\ldots ,n$
, and D is a
$1$
-generalised doubly stochastic matrix with
$\|D\|_2=1$
. -
(2) The column sums satisfy
$|c_1|=\cdots =|c_n|=\sigma $
if and only if
$A=\sigma DW_\gamma $
, where
$W_\gamma :=\operatorname {diag}(e^{i\gamma _1},e^{i\gamma _2},\ldots ,e^{i\gamma _n})$
,
$c_k:=\sigma e^{i\gamma _k}$
, for each
$k=1,\ldots ,n$
, and D is a
$1$
-generalised doubly stochastic matrix with
$\|D\|_2=1$
.
Proof. Suppose that
$|r_1|=\cdots =|r_n|=\sigma $
and write
$r_k=\sigma e^{i\theta _k}$
for each
$k=1,\ldots ,n$
. Then
$A=\sigma W_\theta D$
such that D is a generalised row stochastic matrix with constant row sum
$1$
. Since
$\sigma =\|A\|_2=\|\sigma W_\theta D\|_2=\sigma \|D\|_2$
, it follows that
$\|D\|_2=1$
. By Proposition 2.1(2), D must be a
$1$
-generalised doubly stochastic matrix. The converse is obvious. Statement (2) is proved simply by using the fact that
$\|A^T\|_2=\|A\|_2=\sigma $
and by applying statement (1) to
$A^T$
.
By Proposition 2.4, any matrix of the form
$$ \begin{align*}\sigma \operatorname{diag}(e^{i\theta_1},e^{i\theta_2},\ldots,e^{i\theta_n}) D,\end{align*} $$
where D is a doubly stochastic matrix and
$\theta _1,\theta _2,\ldots ,\theta _n\in \mathbb {R}$
,
$\delta \in \mathbb {R}^+$
, will satisfy the assumption of Corollary 2.3. For example, the matrix
$$ \begin{align*}A:=\begin{bmatrix} {i}/{20}&0&{i}/{20} \\ -{i}/{20}&-{i}/{20}&0 \\ 0&(1+i\sqrt{3})/{40}&(1+i\sqrt{3})/{40} \end{bmatrix}\end{align*} $$
can be written in the form
$$ \begin{align*}A=\frac{1}{10} \operatorname{diag}(e^{i(\pi /2)},e^{i(-\pi /2)},e^{i(\pi /3)})\begin{bmatrix} 1/2&0&1/2\\ 1/2&1/2&0\\ 0&1/2&1/2 \end{bmatrix},\end{align*} $$
where the last matrix is a doubly stochastic matrix. By Corollary 2.3,
$\mu _{\mathbb {B}}(A^m)=(0.1)^m$
for any
$m\in \mathbb {N}$
and any block structure
$\mathbb {B}$
containing
$\operatorname {diag}(e^{i(\pi /2)},e^{i(-\pi /2)},e^{i(\pi /3)})$
. We also observe that the largest (in absolute value) eigenvalue of A is
$0.0488352+0.0447302i$
, which means that
$\rho (A)<\|A\|_2=0.1$
. Thus, A is not a radial matrix and hence not normal.
Note further that if D is a
$1$
-generalised doubly stochastic matrix with
$\|D\|_2=1$
, then
$|D_{ij}|\leq 1$
for each
$i,j\in \{1,2,\ldots ,n\}$
. To see this, note that if
$\|D\|_2=1$
, then
$\|Dx\|\leq \|x\|$
for any nonzero vector
$x\in \mathbb {C}^n$
. So, if
$|D_{ij}|>1$
, by choosing
$x=e_i:=[0,\ldots ,1,\ldots ,0]^T\in \mathbb {C}^n$
(where
$1$
appears only in the ith position),
$$ \begin{align*}\|Dx\|^2=|D_{1j}|^2+\cdots+|D_{ij}|^2+\cdots+|D_{nj}|^2\geq |D_{ij}|^2>1=\|x\|^2,\end{align*} $$
which is a contradiction. If D is a
$1$
-generalised doubly stochastic matrix, then
$\|D\|_2$
need not be
$1$
. For example, the checkerboard matrix
$$ \begin{align*}D:=\begin{bmatrix} 1&-1&1&-1&1\\ -1&1&-1&1&-1\\ 1&-1&1&-1&1\\ -1&1&-1&1&-1\\ 1&-1&1&-1&1\\ \end{bmatrix}\end{align*} $$
is a
$1$
-generalised doubly stochastic matrix with
$\|D\|_2=5$
. To see this, note first that
$Dv=5v$
with
$v=[1,-1,1,-1,1]^T$
, so that
$\rho (D)\geq 5$
. Now,
$$ \begin{align*}5\leq \rho(D)\leq \|D\|_2\leq \|D\|_F:=\sqrt{\textstyle \sum_{i=1}^5\sum_{j=1}^5|D_{ij}|^2}=5.\end{align*} $$
However, there are still many 1-generalised doubly stochastic matrices having spectral norm
$1$
which are not doubly stochastic, as we can see from the following theorem.
Theorem 2.5. Let k be a positive integer. Let
$a,\alpha _1,\alpha _2,\ldots ,\alpha _k$
be positive real numbers and b be a real number.
-
(1) If
$n=2k$
and
$a\geq |b|$
, then the circulant matrix
$C^e(a,b,\alpha )$
having the row vector as the first row will be a
$$ \begin{align*}[a+bi,\; a-bi,\; \alpha_2(a+bi),\; \alpha_2(a-bi),\ldots,\;\alpha_k(a+bi),\;\alpha_k(a-bi)] \end{align*} $$
$\delta _e$
-generalised doubly stochastic matrix of size
$n\times n$
with the spectral norm
$\|C^e(a,b,\alpha )\|_2=\delta _e$
, where
$$ \begin{align*}\delta_e:=2a(1+\alpha_2+\cdots+\alpha_k). \end{align*} $$
-
(2) If
$n=2k+1$
, then the circulant matrix
$C^o(a,b,\alpha )$
having the row vector as the first row will be a
$$ \begin{align*}[a+bi,\; a-bi,\; \alpha_2(a+bi),\; \alpha_2(a-bi),\ldots,\;\alpha_k(a+bi),\;\alpha_k(a-bi),\; \alpha_1]\end{align*} $$
$\delta _o$
-generalised doubly stochastic matrix of size
$n\times n$
with the spectral norm
$\|C^o(a,b,\alpha )\|_2=\delta _o$
, where
$$ \begin{align*}\delta_o:=2a(1+\alpha_2+\cdots+\alpha_k)+\alpha_1.\end{align*} $$
Proof. We first consider the case
$n=2k$
and
$a\geq |b|$
. It is well known that all eigenvalues of the circulant matrix
$C^e(a,b,\alpha )$
are
where
$z=a+bi$
and
$\omega =e^{2\pi i /n}$
. Then, for each
$j\in \{0,1,\ldots ,n-1\}$
,
The triangle inequality becomes an equality when there are nonnegative real numbers
$x_t$
such that
$$ \begin{align*}\alpha_t\omega^{2tj}=x_t\cdot 1=x_t\quad \text{ for each }~t=1,\ldots,k-1.\end{align*} $$
Since
$\alpha _t>0$
,
$x_t$
is a positive real number and thus
$\omega ^{2tj}=1$
for each
$t=1,\ldots ,k-1$
. This implies that
$$ \begin{align*}\omega^{2j}+\omega^{4j} +\cdots+\omega^{2(k-1)j}=k-1\end{align*} $$
and that
$$ \begin{align*}\omega^{4j}+\omega^{6j} +\cdots+\omega^{2kj}=\omega^{2j}(k-1).\end{align*} $$
Subtracting the first equation from the second equation and using
${\omega ^{2kj}=\omega ^{nj}= 1^j=1}$
, we obtain
$\omega ^{2j}-1=(k-1)(1-\omega ^{2j})$
. If
$\omega ^{2j}\neq 1$
, then
$0\leq k-1=-1$
, which is a contradiction. So, the maximum of the
$|\unicode{x3bb} _j|$
can only be reached when
$\omega ^{2j}=1$
, that is, when
$j=0$
or
$j=n/2$
. If
$j=n/2$
, then
$\omega ^j=-1$
and thus
If
$j=0$
, then
$\omega ^j=1$
and thus
Since any circulant matrix is always normal and
$a\geq |b|$
, we conclude that
For the case
$n=2k+1$
, we compute, for each
$j=0,1,\ldots ,n-1$
,
By using the same process as the even case, the inequalities become equalities when
$j=0$
or
$j=n/2$
. Since n is odd, it follows that
$j=0$
and
For example, if
$n=3$
and
$a=1/20, \alpha _1=9/10$
and
$b=-\sqrt {3}/20$
, then the matrix
$$ \begin{align*}C^o:=\begin{bmatrix} {(1-i\sqrt3)}/{20}&{(1+i\sqrt3)}/{20}&{9}/{10}\\ {9}/{10}&{(1-i\sqrt3)}/{20}&{(1+i\sqrt3)}/{20} \\ {(1+i\sqrt3)}/{20}&{9}/{10} &{(1-i\sqrt3)}/{20} \end{bmatrix}\end{align*} $$
is
$1$
-generalised doubly stochastic (but not of course doubly stochastic) having
$1,1,0.7$
as its singular values. By Corollary 2.3,
$\mu _{\mathbb {B}}((C^o)^m)=1$
for any block structure
$\mathbb {B}\subseteq M_3(\mathbb {C})$
and
$$ \begin{align*}\mu_{\mathbb{B}}((\sigma W_\theta C^o)^m)=\sigma^m\end{align*} $$
for any
$m\in \mathbb {N}$
,
$\sigma \in \mathbb {R}^+$
,
$W_\theta :=\operatorname {diag}(e^{i\theta _1},e^{i\theta _2},e^{i\theta _3})\in M_3(\mathbb {C})$
and any block structure
$\mathbb {B}$
containing
$W_\theta $
.
If
$n=4$
and
$a=1,b=-1/2$
and
$\alpha _2=1/3$
so that
$a>|b|$
, then
$$ \begin{align*}C^e:=\begin{bmatrix} {(2-i)}/{2}&{(2+i)}/{2}&{(2-i)}/{6}&{(2+i)}/{6}\\ {(2+i)}/{6}&{(2-i)}/{2}&{(2+i)}/{2}&{(2-i)}/{6}\\ {(2-i)}/{6}&{(2+i)}/{6}&{(2-i)}/{2}&{(2+i)}/{2}\\ {(2+i)}/{2}&{(2-i)}/{6}&{(2+i)}/{6}&{(2-i)}/{2}\\ \end{bmatrix}\end{align*} $$
is an
$8/3$
-generalised doubly stochastic matrix with
$\|C^e\|_2=8/3$
. The condition in statement (1) of Theorem 2.5 is essential. For example, if we choose
$n=4$
,
$a=1,b=2$
and
$\alpha _ 2=3$
, then
$a<|b|$
and the matrix
$$ \begin{align*}E:=\begin{bmatrix} 1+2i&1-2i&3+6i&3-6i\\ 3-6i& 1+2i&1-2i&3+6i\\ 3+6i&3-6i& 1+2i&1-2i\\ 1-2i&3+6i&3-6i& 1+2i\\ \end{bmatrix}\end{align*} $$
is an
$8$
-generalised doubly stochastic matrix having
$\|E\|_2=16$
.
Note that any sum or product of circulant matrices is a circulant matrix. However, a sum of a circulant matrix and a doubly stochastic matrix need not be normal (and hence need not be circulant). For example, the matrix
$$ \begin{align*}& S= C^e +\\& \ \begin{bmatrix} {1}/{4}&0&{3}/{8}&{3}/{8}\\ {1}/{4}& 0&{3}/{8}&{3}/{8}\\ {1}{/4}&{1}/{2}&{5}/{32}&{3}/{32}\\ {1}/{4}&{1}/{2}&{3}/{32}&{5}/{32}\\ \end{bmatrix}= \begin{bmatrix} {(5-2i)}/{4}&{(2+i)}/{2}&{(17-4i)}/{24}&{(17+4i)}/{24} \\ {(7+2i)}/{12}&{(2-i)}/{2}&{(11+4i)}/{8}&{(17-4i)}/{24} \\ {(7-2i)}/{12}&{(5+i)}/{6}&{(37-16i)}/{32}&{(35+16i)}/{32} \\ {(5+2i)}/{4}&{(5-i)}/{6}&{(41+16i)}/{96}&{(37-16i)}/{32}\\ \end{bmatrix}\end{align*} $$
is an
$11/3$
-generalised doubly stochastic matrix with
$\|S\|_2=11/3$
, but it is not normal, as we can see by a direct calculation that
$S^*S\neq SS^*$
.
The conclusion of Corollary 2.3 can be extended to give the following result.
Corollary 2.6. Let
$\tilde {D}_1,\tilde {D}_2,\ldots ,\tilde {D}_k$
be respectively
$\delta _i$
-generalised row (or column) stochastic matrices in
$M_n(\mathbb {C})$
such that
$\|\tilde {D}_i\|_2=\delta _i> 0$
for each
$i=1,2,\ldots , k$
. Then
$S_k(\tilde {D})$
is a
$\delta $
-generalised doubly stochastic matrix in
$M_n(\mathbb {C})$
such that
$\|S_k(\tilde {D})\|_2=\delta $
, where
$\delta :=\delta _1+\delta _2+\cdots +\delta _k$
and, for each
$m\in \mathbb {N}$
and any block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
,
$$ \begin{align*}\mu_{\mathbb{B}}(S_k(\tilde{D})^m)=\delta^m.\end{align*} $$
Proof. By Theorem 2.1(2), the
$D_i$
must be
$\delta _i$
-generalised doubly stochastic matrices. The result follows by exactly the same arguments as in the proof of Corollary 2.3.
Let
$DC(n)$
be the set of all
$n\times n$
doubly circulant matrices in Theorem 2.5 and
$D(n)$
be the set of all doubly stochastic matrices. Let
$\Omega _{D}^{Cir}(n)$
be the set of all
$n\times n$
complex matrices of the form
$$ \begin{align}\Omega_{D}^{Cir}(n):=\bigg\{\sum_{i=1}^sd_iD_i+\sum_{j=1}^t\alpha_jC_j\;\bigg|\; D_i\in D(n), C_j\in DC(n), d_i,\alpha_i\in \mathbb{R}^+_0, s,t\in \mathbb{N}_0\bigg\},\end{align} $$
where
$\mathbb {R}^+_0$
denotes the set of all nonnegative real numbers. Then, by Corollary 2.6, any matrix in
$\Omega _{D}^{Cir}(n)$
satisfies the assumptions of Corollary 2.3 and hence the structured singular value, spectral norm and spectral radius are equal to the constant row sum or column sum, which are independent from the perturbation block structure. From the above discussion, matrices in this class are generalised doubly stochastic and have spectral norm equal to the constant row sum. They are radial but need not be normal.
To sum up, the structured singular values can be calculated explicitly for the class of matrices (which need not be radial nor normal) of the form
$$ \begin{align*} \Omega^m_n(\theta,\gamma,\delta):=\{\delta(W_\theta XW_\gamma)^m\;|\; X\in\Omega_{D}^{Cir}(n);,W_\theta,W_\gamma\in \mbox{Diag}(n), m\in \mathbb{N},\delta\in \mathbb{R}^+ \}, \end{align*} $$
where
$\mbox {Diag}(n):=\{\operatorname {diag}(e^{i\theta _1},e^{i\theta _2},\ldots ,e^{i\theta _n})\;|\; \theta _1,\ldots ,\theta _n\in \mathbb {R}\}\subseteq M_n(\mathbb {C})$
; namely, by Corollary 2.3, if
$X\in \Omega _{D}^{Cir}(n)$
has the constant row (column) sum r, then
$$ \begin{align*}\mu_{\mathbb{B}}(\delta( W_\theta XW_\gamma)^m)=\delta\cdot r^m \end{align*} $$
for any
$W_\theta , W_\gamma \in \mbox {Diag}(n)$
,
$\delta \in \mathbb {R}^+$
,
$m\in \mathbb {N}$
and any complex block structure
$\mathbb {B}\subseteq M_n(\mathbb {C})$
containing
$W_\theta $
and
$W_\gamma $
.
Acknowledgements
The authors would like to thank the anonymous referee(s) for reviewing the manuscript.
