G. R. Belitskii

ON CHAINS OF MATRIX NORMS

(Presented by Academician S. N. Bernstein on 29 I 1963)

Let \(\mathfrak{M}_n\) be the ring of all real square matrices of order \(n\). Consider the set of matrix norms \({}^{(1)}\) in \(\mathfrak{M}_n\) with the relation of partial order defined as the fulfillment of the inequality

\[ \|A\|_1 \leqslant \|A\|_2 \tag{1} \]

for all \(A \in \mathfrak{M}_n\). When condition (1) is fulfilled, one says that the norm \(\|A\|_2\) is a majorant for \(\|A\|_1\) (and \(\|A\|_1\) is a minorant for \(\|A\|_2\)). If, moreover, \(\|A\|_1 < \|A\|_2\) for at least one matrix \(A\), then we shall call \(\|A\|_2\) a strict majorant for \(\|A\|_1\) (respectively, \(\|A\|_1\) a strict minorant for \(\|A\|_2\)).

Next, consider the set of chains* of matrix norms. This set is partially ordered by inclusion and is inductive. By Zorn’s lemma there exists a maximal chain \(Z_0\). It is easy to see that in fact there even exists a continuum of different maximal chains. The question arises as to the possible structure of maximal chains. In the present note we establish the following result, stated as a conjecture by Yu. I. Lyubich.

Theorem. All maximal chains are similar** to the half-line \([0,\infty)\).

We shall precede the proof of this theorem by two lemmas, which are also of independent interest.

We shall call a pseudonorm such a functional in \(\mathfrak{M}_n\) which has all the properties of a matrix norm, with the possible exception of the property of positive definiteness. It can easily be proved that

Lemma 1. Every pseudonorm not identically equal to zero is a matrix norm.

Next, the following lemma on an “intermediate norm” holds.

Lemma 2. Let \(\|A\|_1\) and \(\|A\|_2\) be two matrix norms, and let \(\|A\|_2\) be a strict majorant for \(\|A\|_1\). Then there exists an intermediate matrix norm \(\|A\|\), i.e., a norm which is a strict majorant for \(\|A\|_1\) and a strict minorant for \(\|A\|_2\).

Proof. Put \(\|A\|' = \frac12(\|A\|_1+\|A\|_2)\). The functional \(\|A\|'\) obviously has all the properties of a matrix norm, except, perhaps, the ring property \(\|AB\|' \leqslant \|A\|'\cdot\|B\|'\). If this property is fulfilled, then \(\|A\|'\) will be the required intermediate norm. In the contrary case there exist two matrices \(B\) and \(C\) such that \(\|BC\|' > \|B\|'\cdot\|C\|'\). Put

\[ \|A\|_0=\max_{U\ne 0}\frac{\|AU\|'}{\|U\|'}. \]

Obviously, \(\|A\|_0\) is a matrix norm, and moreover

\[ \|B\|_0 \geqslant \frac{\|BC\|'}{\|C\|'} > \|B\|' \geqslant \|B\|_1. \]

This means that the matrix norm \(\|A\|=\max(\|A\|_0,\|A\|_1)\) is a strict majorant for \(\|A\|_1\). We shall show that this norm is a strict

* In the sense of the introduced partial order.
** In the usual sense for the theory of ordered sets \({}^{(2)}\).

minorant for \(\|A\|_2\). Indeed,

\[ \|A\|_0=\max_{U\ne 0}\frac{\|AU\|}{\|U\|} \leq \max_{U\ne 0} \frac{\|A\|_1\cdot \|U\|_1+\|A\|_2\cdot \|U\|_2} {\|U\|_1+\|U\|_2} \leq \|A\|_2, \]

and, if \(\|A\|_1<\|A\|_2\) for some matrix \(A\), then \(\|A\|_0<\|A\|_2\) and \(\|A\|<\|A\|_2\). The lemma is proved.

Let us proceed to the proof of the theorem. Let \(Z_0\) be some maximal chain. Put \(\nu_0=\inf Z_0\). Obviously, \(\nu_0\) is a pseudonorm. Further, since \(\nu(E)\geq 1\) for any matrix norm \(\nu\), we have \(\nu_0(E)\geq 1\). This means that \(\nu_0\) is a pseudonorm distinct from the identically zero one and, by Lemma 1, is a matrix norm. Since \(Z_0\) is a maximal chain, \(\nu_0\in Z_0\), i.e. \(Z_0\) is closed from below. Obviously, the chain \(Z_0\) is open from above. To prove the theorem it is now sufficient\({}^{2}\) to establish the continuity of \(Z_0\) and the existence in \(Z_0\) of a countable dense set. Consider a section \((P,Q)\) of the chain \(Z_0\). Put \(\nu_1=\sup P\), \(\nu_2=\inf Q\). By maximality of the chain, \(\nu_1,\nu_2\in Z_0\). Further, \(\nu_2=\nu_1\), since otherwise, by Lemma 2, there would be an intermediate norm not belonging to the chain \(Z_0\), contrary to the maximality of \(Z_0\). This means that \(Z_0\) is continuous.

Let us construct a countable dense set in \(Z_0\). For this purpose, note that if \(\nu_1\in Z_0\), \(A\) is some matrix and \(\nu_1(A_0)>\lambda>\nu_0(A_0)\), then there exists a norm \(\nu_2\in Z_0\) such that \(\nu_2(A_0)=\lambda\). Indeed, define a section in \(Z_0\) by putting \(P=\{\nu/\nu(A_0)\leq \lambda\}\), \(Q=\{\nu/\nu(A_0)>\lambda\}\). Since \(\nu_1=\sup P=\inf Q\), it follows that \(\nu_2(A_0)=\lambda\) and, moreover, \(\nu_2\in Z_0\).

Now let \(\mathfrak M=\{A_k\}_{k=1}^{\infty}\) be a countable dense set of matrices in \(\mathfrak M_n\). Put

\[ a_k=\nu_0(A_k),\qquad b_k=\sup_{\nu\in Z_0}\nu(A_k) \]

(where it may turn out that \(b_k=\infty\)). Further, let \(R_k=\{r_{kn}\}_{n=1}^{\infty}\) \((k=1,2,\ldots)\) be a countable dense set on the half-interval \([a_k,b_k)\). Denote by \(\nu_{kn}\) one of those norms \(\nu\in Z_0\) for which \(\nu(A_k)=r_{kn}\). The set of norms \(\{\nu_{kn}\}_{k,n=1}^{\infty}\) is dense in \(Z_0\). Indeed, let \(\nu_1,\nu_2\in Z_0\), and let the norm \(\nu_1\) be a strict majorant for \(\nu_2\). Then there exists a matrix \(A_k\in\mathfrak M\) such that \(\nu_1(A_k)>\nu_2(A_k)\). Let \(\nu_1(A_k)>r_{kn}>\nu_2(A_k)\) \((r_{kn}\in R_k)\). Then the matrix norm \(\nu_{kn}\) is intermediate for \(\nu_1\) and \(\nu_2\). Thus, the set of norms \(\{\nu_{kn}\}_{k,n=1}^{\infty}\) is a countable dense subset of the chain \(Z_0\). The theorem is proved.

Kharkov State University
named after A. M. Gorky

Received
24 I 1963

CITED LITERATURE

1. V. N. Faddeeva, Computational Methods of Linear Algebra, Moscow—Leningrad, 1950.
2. F. Hausdorff, Set Theory, Moscow—Leningrad, 1937.