Zeitschrift für Analysis und ihre Anwendungen

Journal for Analysis and its Applications Volume 18 (1999), No. 2, 175–182

On the Matrix Norm Subordinate to the Hölder Norm

J. Albrecht and P. P. Klein

Dedicated to Prof. L. von Wolfersdorf on the occasion of his retirement

Abstract. For non-negative matrices P the matrix norm subordinate to the Hölder norm of index p with p ∈ (1, ∞) is determined by an eigenvalue problem T α = λα, where T is a homogeneous, strongly monotone operator.

Keywords: Hölder vector norms, subordinate matrix norms, non-negative matrices

AMS subject classification: Primary 15 A 60, 15 A 18, secondary 47 H 07

1. Introduction

Assume v ∈ ℝ^{n} and M ∈ ℝ^{m×n}. For the Hölder vector norm

∥v∥_{p} = \{ \begin{matrix}[∑_{i=1}^{n} |v_{i}|^{p}]^{1/p} & for 1 ≤ p < ∞ \\ max_{i=1,...,n}|v_{i}| & for p = ∞ \end{matrix}

the subordinate matrix norm

∥M∥_{p} = max_{v∈ℝ^{n}\\{0\}} \frac{∥Mv∥_{p}}{∥v∥_{p}} (1 ≤ p ≤ ∞)

can be easily calculated in the limiting cases:

∥M∥_{1} = max_{j=1,...,n} ∑_{i=1}^{m} |m_{ij}|  and  ∥M∥_{∞} = max_{i=1,...,m} ∑_{j=1}^{n} |m_{ij}|.

Furthermore, the spectral norm is well known:

∥M∥_{2} = [ρ(M^{T} M)]^{1/2}.

Beyond that in the special case of non-negative matrices P ∈ ℝ_{+}^{m×n} for all p ∈ (1, ∞) the matrix norm ∥P ∥_{p} can be determined by an eigenvalue problem, which is nonlinear for p ≠ 2.

J. Albrecht: Techn. Univ. Clausthal, Inst. Math., Erzstr. 1, D-38678 Clausthal-Zellerfeld P. P. Klein: Techn. Univ. Clausthal, Rech.-Zentrum, Erzstr. 51, D-38678 Clausthal-Zellerfeld ISSN 0232-2064 / $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag Berlin

2. The eigenvalue problem

Let P ∈ ℝ_{+}^{m×n}, p ∈ (1, ∞) and (p − 1)(q − 1) = 1. Because of |P v| ≤ P |v| for v ∈ ℝ^{n},

∥P ∥_{p} = max_{v∈ℝ_{+}^{n}\\{0\}} \frac{∥P v∥_{p}}{∥v∥_{p}}  (1)

holds. Discussing this maximum problem leads to

Definition 1.

T : ℝ_{+}^{n} → ℝ_{+}^{n},  (T v)_{j} = [∑_{i=1}^{m} p_{ij}(P v)_{i}^{p−1}]^{q−1}  (j = 1, …, n)  (2)

and

Theorem 1. Assume that the eigenvalue problem

T α = λα  (3)

has an eigenvector α with positive components only, corresponding to a positive eigenvalue λ. Then

∥P ∥_{p} = λ^{1/q}.  (4)
Proof. 1.1 In the case (P α)_{i} > 0, for v ∈ ℝ_{+}^{n},

(P v)_{i} = ∑_{j=1}^{n} p_{ij}v_{j} = ∑_{j=1}^{n} p_{ij}α_{j} \frac{v_{j}}{α_{j}} = (P α)_{i} \frac{∑_{j=1}^{n} p_{ij}α_{j} \frac{v_{j}}{α_{j}}}{∑_{j=1}^{n} p_{ij}α_{j}}

holds and Hölder’s inequality for convex functions φ (see [6, 8])

φ (\frac{∑_{j} p_{j}t_{j}}{∑_{j} p_{j}} ) ≤ \frac{∑_{j} p_{j}φ(t_{j})}{∑_{j} p_{j}}

yields

(P v)_{i}^{p} ≤ (P α)_{i}^{p} \frac{∑_{j=1}^{n} p_{ij}α_{j}(\frac{v_{j}}{α_{j}})^{p}}{∑_{j=1}^{n} p_{ij}α_{j}} = (P α)_{i}^{p−1} ∑_{j=1}^{n} \frac{p_{ij}}{α_{j}^{p−1}} v_{j}^{p}.

1.2 In the case (P α)_{i} = 0, because of α_{j} > 0 (j = 1, …, n), p_{ij} = 0 (j = 1, …, n) holds and therefore (P v)_{i} = 0 is valid for all v ∈ ℝ_{+}^{n}.

2. Hence it follows that

∑_{i=1}^{m}(P v)_{i}^{p} ≤ ∑_{j=1}^{n} \frac{∑_{i=1}^{m} p_{ij}(P α)_{i}^{p−1}}{α_{j}^{p−1}} v_{j}^{p} = ∑_{j=1}^{n} \frac{(T α)_{j}^{p−1}}{α_{j}^{p−1}} v_{j}^{p} = λ^{p−1} ∑_{j=1}^{n} v_{j}^{p}

and

∥P v∥_{p} ≤ λ^{1/q}∥v∥_{p}.

If v = α, then equality holds

The theorem is illustrated by the following

Example (f ∈ ℝ_{+}^{m}, g ∈ ℝ̊_{+}^{n}).

P = fg^{T} : α = (g_{i}^{q−1})_{i=1}^{n}, ∥P ∥_{p} = ∥f∥_{p}∥g∥_{q}.

The assumption that the eigenvalue problem T α = λα has an eigenvector α with positive components only, corresponding to a positive eigenvalue λ, will be shown to be fulfilled if P^{T} P is irreducible.

3. P^{T} P irreducible

In a real linear space X let the cone K define the partial ordering ≤. Eigenvalue problems with operators T : K → K having the properties

1. T is monotone on K, i.e. u, v ∈ K with u ≤ v implies T u ≤ T v

2 T is homogeneous on K, i.e. T (cv) = cT v for c ≥ 0 and v ∈ K

3. T is completely continuous on K

have been investigated by Krein and Rutman [7] and by Bohl [2]. The results in [2] necessitate another assumption, namely that T is strongly monotone on K. In the case X = ℝ^{n}, K = ℝ_{+}^{n} this means the following.

Definition 2. An operator T being monotone on ℝ_{+}^{n} is called strongly monotone on ℝ_{+}^{n}, if for all v, w ∈ ℝ_{+}^{n} with v ≤ w and v ≠ w there exists a number μ ∈ ℕ such that

(T^{μ}v)_{j} < (T^{μ}w)_{j} (j = 1, …, n)

holds.

By the following lemma the strong monotonicity of the operator T defined in (2) can be concluded from the strong monotonicity of P^{T} P.

Lemma 1. Assume P ∈ ℝ_{+}^{m×n} and p ∈ (1, ∞). For arbitrary vectors v, w ∈ ℝ_{+}^{n} with v ≤ w, all ν ∈ ℕ and each fixed j ∈ {1, …, n} the equivalence

(T^{ν}v)_{j} = (T^{ν}w)_{j} ⟺ ((P^{T} P)^{ν}v)_{j} = ((P^{T} P)^{ν}w)_{j}.  (5)

holds.

Proof. 1. ν = 1: Let j ∈ {1, …, n} be fixed. Then (T v)_{j} = (T w)_{j} is equivalent to

∑_{i=1}^{m} p_{ij}((P w)_{i}^{p−1} − (P v)_{i}^{p−1}) = 0.  (6)

As v ≤ w implies P v ≤ P w and (P v)_{i}^{p−1} ≤ (P w)_{i}^{p−1} (i = 1, …, m), all terms of (6) are non-negative. For every i ∈ {1, …, m} with p_{ij} > 0 equation (6) requires that (P w)_{i}^{p−1} − (P v)_{i}^{p−1} = 0, yielding (P (w − v))_{i} = 0. Therefore

∑_{i=1}^{m} p_{ij}(P (w − v))_{i} = 0  (7)

follows and thus (P^{T} P v)_{j} = (P^{T} P w)_{j} holds. Analogously (6) can be deduced from (7).

2. Induction from ν to ν + 1: Let j ∈ {1, …, n} be fixed. As T is monotone, v ≤ w implies T^{ν}v ≤ T^{ν}w. Define ṽ = T^{ν}v and w̃ = T^{ν}w. Using (5) with ν = 1 leads to

(T ṽ)_{j} = (T w̃)_{j} ⟺ (P^{T} P ṽ)_{j} = (P^{T} P w̃)_{j}

i.e. (T^{ν+1}v)_{j} = (T^{ν+1}w)_{j} is equivalent to

∑_{k=1}^{n}(P^{T} P)_{jk}(T^{ν}w − T^{ν}v)_{k} = 0.  (8)

As all terms in (8) are non-negative, (T^{ν}w − T^{ν}v)_{k} = 0 holds for every k ∈ {1, …, n} with (P^{T} P)_{jk} > 0. Since (5) is assumed to be true for ν,

∑_{k=1}^{n}(P^{T} P)_{jk}((P^{T} P)^{ν}(w − v))_{k} = 0  (9)

follows and thus ((P^{T} P)^{ν+1}v)_{j} = ((P^{T} P)^{ν+1}w)_{j} is obtained. In the same way (8) can be concluded from (9)

Theorem 2. Assume P ∈ ℝ_{+}^{m×n}, p ∈ (1, ∞) and P^{T} P irreducible. Then:

1. P^{T} P and T are strongly monotone on K.

2. The eigenvalue problem T α = λα has an eigenvector α with positive components only, corresponding to a positive eigenvalue λ.

Proof. 1. All diagonal elements of P^{T} P are positive. Assuming the contrary, namely that (P^{T} P)_{jj} = 0 for at least one j ∈ {1, …, n}, all elements of the j-th column of P would be zero. This would imply P^{T} P to be reducible, in contradiction to the assumption.

Since P^{T} P is irreducible and as its diagonal elements are positive, [2: p. 111/Theorem 2.3] says that (P^{T} P)^{n−1} consists of positive elements only, i.e. P^{T} P is strongly monotone. Using Lemma 1 for ν = n − 1 proves that T is strongly monotone as well.

2. As the operator T is completely continuous and strongly monotone, by [2: p. 53/Theorem 2.7] with S = T, T has an eigenvector α with positive components only and a corresponding positive eigenvalue λ

Example. Doubly stochastic matrices, e.g.

P = \frac{1}{15} ( \begin{matrix}4 & 9 & 2 \\ 3 & 5 & 7 \\ 8 & 1 & 6 \end{matrix} ) : α = ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) , ∥P ∥_{p} = 1.

Theorem 3. Assume P ∈ ℝ_{+}^{m×n}, p ∈ (1, ∞) and P^{T} P irreducible. Starting from α^{(1)} ∈ ℝ_{+}^{n} having positive components only, the iterates α^{(k+1)} defined by

α^{(k+1)} := T α^{(k)}  (k ∈ ℕ)  (10)

have the same property. With

\underline{λ}^{(k)} := min_{j=1,...,n} \frac{α_{j}^{(k+1)}}{α_{j}^{(k)}} and \overline{λ}^{(k)} := max_{j=1,...,n} \frac{α_{j}^{(k+1)}}{α_{j}^{(k)}}  (k ∈ ℕ)  (11)

the eigenvalue inclusion

\underline{λ}^{(1)} ≤ … ≤ \underline{λ}^{(k)} ≤ \underline{λ}^{(k+1)} ≤ … ≤ λ ≤ … ≤ \overline{λ}^{(k+1)} ≤ \overline{λ}^{(k)} ≤ … ≤ \overline{λ}^{(1)} (12)

is obtained. Furthermore,

lim_{k→∞} \underline{λ}^{(k)} = λ = lim_{k→∞} \overline{λ}^{(k)}  (13)

holds.

Proof. The monotonicity and the convergence of the sequences \{\underline{λ}^{(k)}\}_{k∈ℕ} and \{\overline{λ}^{(k)}\}_{k∈ℕ} follow from [2, p. 53/Theorem 2.7] as well

Remark. For p = 2 Theorem 3 reduces to the inclusion theorem of Collatz [3] for non-negative irreducible matrices applied to P^{T} P.

4. P^{T} P reducible

Allowing P^{T} P to be reducible, it may be assumed that P^{T} P already has the normal block diagonal form of symmetric reducible matrices [9]. Otherwise the columns of P have to be permuted appropriately, which implies the same permutations for the rows of P^{T} and thus results in the normal form of P^{T} P. Permuting the columns of P has no effect on ∥P ∥_{p}.

According to the number and the sizes of the diagonal submatrices of P^{T} P, the matrix P ∈ ℝ_{+}^{m×n} is split up into column blocks

P = (P_{1}, …, P_{s})  with P_{σ} ∈ ℝ_{+}^{m×n_{σ}}  (σ = 1, …, s).  (14)

Correspondingly, a vector v ∈ ℝ_{+}^{n} is decomposed as

v = ( v_{1} ; ⋮ ; v_{s} )  with v_{σ} ∈ ℝ_{+}^{n_{σ}}  (σ = 1, …, s).  (15)

The block structure of P^{T} P implies

P_{ρ}^{T} P_{σ} = Θ_{ρσ} ∈ ℝ_{+}^{n_{ρ}×n_{σ}} (ρ ≠ σ; ρ, σ = 1, …, s)

which means that each non-zero row of P has non-zero elements exactly in one column block of P. Therefore, taking notice of (15),

∥P v∥_{p}^{p} = ∑_{σ=1}^{s} ∥P_{σ}v_{σ}∥_{p}^{p}  (v ∈ ℝ_{+}^{n})  (16)

holds.

Theorem 4. Assume P ∈ ℝ_{+}^{m×n} and p ∈ (1, ∞). Let P^{T} P be reducible such that

P^{T} P = diag (P_{1}^{T} P_{1}, …, P_{s}^{T} P_{s})  (17)

and assume each diagonal submatrix P_{σ}^{T} P_{σ} (σ = 1, …, s) to be irreducible. Consequently, the eigenvalue problem (3) is split up into subproblems of the same type

T_{σ}α_{σ} = λ_{σ}α_{σ}  (σ = 1, …, s)  (18)

where each T_{σ} : ℝ_{+}^{n_{σ}} → ℝ_{+}^{n_{σ}} results from (2) with P_{σ} instead of P. Then

∥P ∥_{p} = λ^{1/q}  with λ = max_{σ=1,...,s} λ_{σ}  (19)

holds.

Proof. For each eigenvalue problem (18) Theorem 2 guarantees the existence of an eigenvector α_{σ} with positive components only, corresponding to a positive eigenvalue λ_{σ}. Therefore Theorem 1 ensures

∥P_{σ}v_{σ}∥_{p}^{p} ≤ λ_{σ}^{p−1}∥v_{σ}∥_{p}^{p} (v_{σ} ∈ ℝ_{+}^{n_{σ}}, σ = 1, …, s)

with equality, if v_{σ} = α_{σ} (σ = 1, …, s). For v ∈ ℝ_{+}^{n}, using (16),

∥P v∥_{p}^{p} = ∑_{σ=1}^{s} ∥P_{σ}v_{σ}∥_{p}^{p} ≤ ∑_{σ=1}^{s} λ_{σ}^{p−1}∥v_{σ}∥_{p}^{p} ≤ λ^{p−1} ∑_{σ=1}^{s} ∥v_{σ}∥_{p}^{p} = λ^{p−1}∥v∥_{p}^{p}

follows, implying

∥P v∥_{p} ≤ λ^{1/q}∥v∥_{p}.

Equality holds, if v satisfies

v_{σ} = \{ \begin{matrix}α_{σ} & for λ_{σ} = λ \\ θ_{σ} & for λ_{σ} < λ \end{matrix} (σ = 1, …, s)

Remark. Since permuting the rows of P leaves P^{T} P as well as ∥P ∥_{p} unchanged, additional splittings of P ∈ ℝ_{+}^{m×n} into row blocks can be obtained such that

P = (P_{ρσ})  with P_{ρσ} ∈ ℝ_{+}^{m_{ρ}×n_{σ}}  (ρ, σ = 1, …, s)

and, with π denoting any permutation of {1, …, s}, each column block P_{σ} has exactly one non-zero subblock P_{π(σ) σ} (σ = 1, …, s).

Example (f ∈ R_{+}^{m−1}, g ∈ ℝ̊_{+}^{n−1}).

P = ( \begin{matrix}Θ & f \\ g^{T} & 0 \end{matrix} ) : ∥P ∥_{p} = max\{∥f∥_{p}, ∥g∥_{q}\}.

Theorem 4 is supplemented by the following

Remark. Allowing P^{T} P to have a zero diagonal submatrix P_{σ^{∗}}^{T}P_{σ^{∗}} resulting from a zero column block P_{σ^{∗}}, then T_{σ^{∗}} is the zero operator with the eigenvalue λ_{σ^{∗}} = 0. This leaves the result of Theorem 4 unchanged.

On the Matrix Norm Subordinate to the Hölder Norm 181

5. Numerical example

Applying discretization methods to boundary value problems with partial differential equations, often leads to linear systems

v = P v + r  (20)

with non-negative matrices P. If P is symmetric, ρ(P) = ∥P ∥_{2} ≤ ∥P ∥_{p} for 1 ≤ p ≤ ∞ holds. In case P is non-symmetric, however, p^{∗} with ∥P ∥_{p^{∗}} = min{∥P ∥_{p}| 1 ≤ p ≤ ∞} is generally not known in advance.

Applying the finite difference method to the boundary value problem [5]

\begin{matrix}−(u_{xx} + u_{yy} + \frac{3}{5 − y} u_{y}) & = 1  in B = (−\frac{1}{2}, \frac{1}{2}) × (−1, 1) \\ u & = 0  on ∂B \end{matrix} \}

red-black ordering of the unknowns generates linear systems (20) with P non-symmetric, non-negative and P^{T} P reducible:

P = ( \begin{matrix}Θ_{11} & P_{12} \\ P_{21} & Θ_{22} \end{matrix} ) ,  and  P^{T} P = ( \begin{matrix}P_{21}^{T}P_{21} & Θ_{12} \\ Θ_{21} & P_{12}^{T}P_{12} \end{matrix} ) .  (21)

For different mesh widths h the following results were obtained by discretely minimizing ∥P ∥_{p} with respect to p in a finite interval:

\begin{matrix}h & n & ρ(P) & p^{∗∗} & ∥P ∥_{p^{∗∗}} & ∥P ∥_{2} \\ \frac{1}{6} & 33 & 0.91496 & 2.71 & 0.94058 & 0.94608 \\ \frac{1}{8} & 60 & 0.95175 & 2.99 & 0.97062 & 0.97689 \\ \frac{1}{12} & 138 & 0.97843 & 3.62 & 0.99003 & 0.99690 \\ \frac{1}{16} & 248 & 0.98784 & 4.38 & 0.99587 & 1.00289 \\ \frac{1}{24} & 564 & 0.99459 & 6.79 & 0.99915 & 1.00632 \\ \frac{1}{32} & 1008 & 0.99696 & 12.6 & 0.99986 & 1.00719 \end{matrix}

Table 1: Discrete minimization of ∥P ∥_{p}

Rewriting the boundary value problem in self-adjoint form [5]

\begin{matrix}− ([\frac{1}{(5 − y)^{3}} u_{x}]_{x} + [\frac{1}{(5 − y)^{3}} u_{y}]_{y}) & = \frac{1}{(5 − y)^{3}} in B, \\ u & = 0 on ∂B \end{matrix} \}

and applying the finite difference method with red-black ordering of the unknowns again, linear systems (20), (21) are obtained, where P now is symmetric and non-negative. The spectral radii ρ(P) in this case are slightly above those given in Table 1.

References

[1] Albrecht, J.: Minimal norms of nonnegative irreducible matrices. Lin. Alg. Appl. 249 (1996), 255 – 258.

[2] Bohl, E.: Monotonie: Lösbarkeit und Numerik bei Operatorgleichungen. Berlin: Springer Verlag 1974.

[3] Collatz, L.: Einschließungssatz für die charakteristischen Zahlen von Matrizen. Math.Z. 48 (1942), 221 – 226.

[4] Collatz, L.: Funktionalanalysis und Numerische Mathematik. Berlin: Springer Verlag 1964.

[5] Collatz, L.: The Numerical Treatment of Differential Equations. Berlin: Springer Verlag 1966.

[6] Hölder, L. O.: Über einen Mittelwertsatz. Nachr. Ges. Wiss. Göttingen 1889, 38 – 47.

[7] Krein, M. G. and M. A. Rutman: Linear operators leaving invariant a cone in a Banach space. AMS Transl. (Series One) 10 (1962), 307 – 320.

[8] Polya, G. and G. Szegö: Problems and Theorems in Analysis (Vol. 1). New York: Springer Verlag 1978.

[9] Varga, R. S.: Matrix Iterative Analysis. Englewood Cliffs: Prentice Hall Inc. 1962.

Received 02.06.1998