Finding Norms of Hadamard Multipliers

C. C. Cowen,^{∗} Purdue University, West Lafayette, Indiana P. A. Ferguson, Purdue University, West Lafayette, Indiana D. K. Jackman, Wooster College, Wooster, Ohio E. A. Sexauer, University of Richmond, Richmond, Virginia C. Vogt, Purdue University, West Lafayette, Indiana and H. J. Woolf Purdue University, West Lafayette, Indiana

Submitted by Roger A. Horn

ABSTRACT

The norm of a matrix B as a Hadamard multiplier is the norm of the map X ↦ X^{•}B, where ^{•} is the Hadamard or entrywise product of matrices. Watson proposed an algorithm for finding lower bounds for the Hadamard multiplier norm of a matrix. It is shown how Watson’s algorithm can be used to give upper bounds as well which, in many cases, yield the Hadamard multiplier norm to any desired accuracy. A sharp form of Wittstock’s decomposition theorem is proved for the special case of Hadamard multiplication.

∗Supported in part by a grant from the National Science Foundation including support from the REU program for all but the first author.

LINEAR ALGEBRA AND ITS APPLICATIONS xxx:1–xxx (1993) 1

\begin{matrix}c \\ ◯ \end{matrix} Elsevier Science Publishing Co., Inc., 1993 655 Avenue of the Americas, New York, NY 10010 0024- 3795/93/$6.00

1. INTRODUCTION

By the Hadamard product, also called the Schur product, we mean the entry–wise product of matrices: if A and B are m × n matrices, their Hadamard product, A^{•}B is the m × n matrix whose entries are a_{jk}b_{jk}. In this paper, we study the operator on the set M_{n} of n × n real matrices given by X ↦ X^{•}B, for a fixed B. For a matrix X in M_{n}, ∥X∥_{sp} will denote its spectral norm (i.e., the largest singular value of X) and the norm K_{B} of the Hadamard multiplier is its norm as an operator on M_{n} with the spectral norm, that is,

K_{B} = max{∥X^{•}B∥_{sp} : ∥X∥_{sp} ≤ 1}

Recently, Watson [15] proposed an algorithm for finding, among other things, a lower bound for K_{B}. Using a factorization result of [3] based on the factorization theorem of Haagerup [6, 12], we show how to use Watson’s algorithm to give an upper bound for K_{B} as well. In many interesting cases, for example the triangular truncation matrices studied in [3] or McEachin’s matrices studied in [11, 5], the upper and lower bounds agree. (Sample results from the algorithm coded in Matlab [10] are included.) Hadamard multiplication is an example of a completely bounded map [12]; we give a sharp form of Wittstock’s decomposition theorem for completely bounded maps in the special case of Hadamard multiplication by a Hermitian matrix. This result could, in principle, also be used to find K_{B} when B is Hermitian, but the resulting optimization problem does not seem likely to lead to a rapidly converging algorithm. However, if B is Hermitian with rank 2, this formulation does lead to a relatively simple one variable optimization problem that can be solved explicitly. More information about the Hadamard product and its properties can be found in [7].

The authors would like to thank the referees for several helpful suggestions that led to improvements and simplifications of our presentation.

2. WATSON’S ALGORITHM

Throughout, ⟨·, ·⟩ will denote the standard Euclidean inner product on R^{n} and by the norm of a vector, we will mean the Euclidean norm. If P is in M_{n}, we will denote its (Hilbert space) adjoint, that is, its transpose, by P ∗. Much of what is presented here can be immediately generalized to the complex case, but the algorithm is designed for the real case.

First of all, we want to reinterpret Watson’s algorithm which he motivated by use of subgradients in the context of convex optimization. We think of Hadamard multiplication by B as a linear transformation on the vector space M_{n}. The dual of M_{n} as a vector space is isomorphic to M_{n} where, for G in M_{n}, the linear functional Λ_{G} is defined by

Λ_{G}(X) = trace(G∗X)

Regarding M_{n} as normed space with the spectral norm, its dual space is normed by the trace norm

∥Λ_{G}∥ = ∥G∥_{tr} = max{trace(V ∗G) : ∥V ∥_{sp} = 1}

that is, the trace norm of G is the sum of the singular values of G. For B, G, and X in M_{n}, the identity

Λ_{G}(B^{•}X) = trace(G∗(B^{•}X)) = trace((B^{•}G)∗X) = Λ_{B•G}(X)

shows that the dual of Hadamard multiplication by B is again Hadamard multiplication by B. Since the norm of a transformation and its dual are the same, we have

K_{B} = max{∥G^{•}B∥_{tr} : ∥G∥_{tr} ≤ 1}

Our interpretation of Watson’s algorithm is that it finds successively better estimates for the norm and the dual norm of Hadamard multiplication by B. Notice that since the unitaries are the extreme points of the unit ball of M_{n} with the spectral norm and the rank one matrices of norm 1 are the extreme points of the unit ball of M_{n} with the trace norm that the Hadamard multiplier norm is achieved at such matrices. Moreover, using singular value decomposition, given a matrix H in M_{n}, it is easy to find a unitary matrix U so that ∥H∥_{tr} = trace(H∗U) and a rank one matrix G with ∥G∥_{tr} = 1 so that ∥H∥_{sp} = trace(G∗H). Specifically, if H = V DW ∗ is the singular value decomposition of H where V and W are unitary and D is the diagonal matrix whose diagonal entries are the singular values of H arranged in non–increasing order, then letting U = V W ∗,

∥H∥_{tr} = trace(D) = trace(W ∗(W DV ∗)V)
= trace((W DV ∗)(V W ∗)) = trace(H∗U)  (1)

Similarly, letting G = xy∗ where x and y are the first columns of V and W respectively,

∥H∥_{sp} = trace(x∗V DW ∗y) = trace(yx∗V DW ∗) = trace(G∗H) (2)

With this in mind, we can easily describe Watson’s algorithm.

Watson’s Algorithm

Choose a unitary matrix U_{0}.

For k = 1 to Kstop

s_{k} = ∥B^{•}U_{k−1}∥_{sp}
Choose G_{k} rank one with ∥G_{k}∥_{tr} = 1
and trace(G∗_{k}(B^{•}U_{k−1})) = s_{k}
t_{k} = ∥B^{•}G_{k}∥_{tr}
Choose U_{k} unitary with trace((B^{•}G_{k})∗U_{k}) = t_{k}

End Since

s_{k} = ∥B^{•}U_{k−1}∥_{sp} ≤ K_{B}∥U_{k−1}∥_{sp} = K_{B}

and

t_{k} = ∥B^{•}G_{k}∥_{tr} ≤ K_{B}∥G_{k}∥_{tr} = K_{B}

the sequences of estimates s_{k} and t_{k} are bounded. Moreover, for each k,

s_{k+1} = ∥B^{•}U_{k}∥_{sp}
= max{trace(G∗(B^{•}U_{k})) : rank(G) = 1 and ∥G∥_{tr} = 1}
≥ trace(G∗_{k}(B^{•}U_{k})) = trace((B^{•}G_{k})∗U_{k}) = t_{k}

and

t_{k} = ∥B^{•}G_{k}∥_{tr} = max{trace((B^{•}G_{k})∗U) : U is unitary}
≥ trace((B^{•}G_{k})∗U_{k−1}) = trace(G∗_{k}(B^{•}U_{k−1})) = s_{k}

so that

s_{1} ≤ t_{1} ≤ s_{2} ≤ t_{2} ≤ ⋯ ≤ K_{B}

It follows that the estimates s_{k} and t_{k} converge to a lower bound for K_{B} and that, by possibly choosing subsequences, we can find a unitary matrix U_{∞} and a rank one matrix G_{∞} with ∥G_{∞}∥_{tr} = 1 so that

lim s_{k} = lim t_{k} = ∥(B^{•}G_{∞})∥_{tr} = ∥(B^{•}U_{∞})∥_{sp} ≤ K_{B}

Naturally, we hope that the limits are actually equal to K_{B} and this does happen for some interesting matrices B. However, it does not always happen; indeed, taking U_{0} = I just gives the limit equal to the largest absolute value diagonal entry, not always the same as K_{B}. We need a good upper estimate of K_{B} in order to decide if a particular lower estimate is giving acceptable results.

For P an n × n matrix with columns P_{1}, P_{2}, ⋯, P_{n}, let

c(P) = max{∥P_{1}∥, ∥P_{2}∥, ⋯, ∥P_{n}∥}

Haagerup [6] (or see [12, pp. 110–116], [1], [13], or [9]) showed that if B is an n × n matrix then the norm of B as a Hadamard multiplier is

K_{B} = min{c(S)c(R) : S∗R = B}

We will need the following extension of Haagerup’s theorem from [3].

Theorem A. Let B be a non–zero n × n matrix. If S and R are n × n matrices and S∗R = B is a factorization of B with c(S) = c(R) = \sqrt{K_{B}}, there is a unitary matrix U and unit vectors x and y so that if X and Y are the diagonal matrices with diagonals x and y, then

K_{B} = ⟨B^{•}Uy, x⟩ = trace((xy∗)∗B^{•}U) = ∥B^{•}U∥_{sp}

RY U∗ = SX, and the columns satisfy ∥S_{j}∥ = c(S) and ∥R_{k}∥ = c(R) whenever the components x_{j} and y_{k} are non-zero. Conversely, if S and R are n × n matrices satisfying B = S∗R and x and y are unit vectors such that ∥S_{j}∥ = ∥R_{k}∥ = c(S) = c(R) whenever x_{j} and y_{k} are non-zero and U is a unitary matrix so that RY U∗ = SX, then K_{B} = c(R)c(S) = ∥B^{•}U∥_{sp}.

We want to use the convergents coming from Watson’s algorithm to find a factorization of B. Since every factorization of B gives an upper bound for K_{B} and Watson’s algorithm gives a lower bound, we hope to obtain accurate estimates for the Hadamard multiplier norm.

Suppose the G’s and U’s are chosen successively as in the outline of Watson’s algorithm above where U_{k} = V_{k}W ∗_{k} and G_{k} = x_{k}y∗_{k} using the singular value decomposition B^{•}(x_{k}y∗_{k}) = V_{k}D_{k}W ∗_{k} as in equations (1) and (2) and s_{k} = ∥B^{•}U_{k−1}∥_{sp} and t_{k} = ∥B^{•}G_{k}∥_{tr}. If s, t, x, y, D, V, and W are the limits (perhaps of subsequences) of s_{k}, t_{k}, x_{k}, y_{k}, D_{k}, V_{k}, W_{k} respectively, then s = t, ∥x∥ = ∥y∥ = 1, V and W are unitary and satisfy

B^{•}(xy∗) = V DW ∗

and

s = ∥B^{•}(xy∗)∥_{tr} = trace ((V W ∗)∗B^{•}(xy∗))
= trace ((xy∗)∗B^{•}(V W ∗)) = ∥B^{•}(V W ∗)∥_{sp}

Now let X and Y be the diagonal matrices with diagonals x and y so that B^{•}(xy∗) = XBY. If X and Y are invertible, letting C be the non–negative diagonal matrix with C^{2} = D, then

XBY = B^{•}(xy∗) = V DW ∗ = V C^{2}W ∗

implies

B = (X^{−1}V C)(CW ∗Y^{−1})

Taking

S = CV ∗X^{−1} and R = CW ∗Y^{−1}  (3)

and U = V W ∗, we have B = S∗R,

RY U∗ = (CW ∗Y^{−1})Y (V W ∗)∗ = CV ∗ = (CV ∗X^{−1})X = SX

and ∥B^{•}U∥_{sp} = s.

While these conditions are not quite enough for the converse statement of Theorem A, this factorization is highly suggestive. Moreover, it indicates the need for investigating the conditions under which X and Y are not invertible. The last section of the paper gives some results of using the authors’ Matlab code implementing Watson’s algorithm to give a lower bound for K_{B} and using the factorization suggested above to give an upper bound. For the triangular truncation matrices and McEachin’s matrices, the resulting X and Y are invertible and the computed values of the upper and lower bounds differ by less than 2 × 10^{−14} for sizes up to 50 × 50; in other words, for these matrices, the algorithm works to machine accuracy. (In addition, checking the extra hypotheses in the converse statement from Theorem A shows that the computed matrices satisfy (up to machine accuracy) these hypotheses, so the theory indicates they should give K_{B}.)

It is easy to see that if B is a matrix for which x and y are the standard unit basis vectors e_{i} and e_{j}, then K_{B} = ∥B^{•}(xy∗)∥_{tr} = |b_{ij}|, so the Hadamard multiplier norm of B is given by one of its entries. More generally, if B̂ is the submatrix of B whose rows and columns are associated with the non–zero components of x and y, then constructing the vectors x̂ and ŷ by omitting the zero components, we have

K_{B} = ∥B^{•}(xy∗)∥_{tr} = ∥B̂^{•}(x̂y∗)∥_{tr} ≤ K_{B} ≤ K_{B}

That is, the non–invertible X and Y are associated with submatrices of B that have the same Hadamard multiplier norm.

We will say a matrix B is Hadamard irreducible if there are no proper submatrices of B with the same Hadamard multiplier norm as B. In our experience, a large difference between the computed upper and lower bounds for K_{B} is due to the presence of a submatrix with a large multiplier norm (as compared with K_{B}), that is, with matrices that are reducible in this sense. Indeed, in such cases, the sequences x_{k} and y_{k} converge to vectors whose non–zero components are associated with just such a submatrix. Further analysis of this situation suggests a multistep procedure for finding an optimal Haagerup factorization in this case as well. Our analysis, below, of the case in which a proper submatrix has the same Hadamard multiplier norm as B leads to Theorem 2.1 which is the formal justification of the multistep procedure. The application of Theorem 2.1 in finding norms is illustrated in section 4.

Suppose B is an n × n matrix with block form

( \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} )

where B_{11} is invertible, Hadamard irreducible, and K_{B_{11}} = K_{B}. Let B = S∗R be a factorization of B as in Theorem A. By multiplying S and R on the left by an appropriate unitary, we may assume without loss of generality that S is upper triangular. In block form, this is

( \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} ) = ( \begin{matrix}S∗_{11} & 0 \\ S∗_{12} & S∗_{22} \end{matrix} ) ( \begin{matrix}R_{11} & R_{12} \\ R_{21} & R_{22} \end{matrix} )

In particular, we have B_{11} = S∗_{11}R_{11}. Since

c(S_{11})c(R_{11}) ≤ c(S)c(R) = K_{B} = K_{B_{11}} ≤ c(S_{11})c(R_{11})

we see that in fact c(S_{11}) = c(R_{11}) = \sqrt{K_{B}}. But B_{11} is Hadamard irreducible, so each column of S_{11} and R_{11} has the same norm and the inequality

K_{B} = K_{B_{11}} = c(R_{11})^{2} ≤ c(R_{11})^{2} + c(R_{21})^{2} = c(R)^{2} = K_{B}

shows that R_{21} = 0.

The invertibility of B_{11} implies that S_{11} and R_{11} are invertible also and it follows that S_{12} = (R∗_{11})^{−1}B∗_{21} and R_{12} = (S∗_{11})^{−1}B_{12}. Since

B_{22} = S∗_{12}R_{12} + S∗_{22}R_{22} = B_{21}R_{11}^{−1}(S∗_{11})^{−1}B_{12} + S∗_{22}R_{22}

Substituting, we find

S∗_{22}R_{22} = B_{22} − B_{21}B_{11}^{−1}B_{12}

which we will denote by A. (In particular, K_{A} ≤ K_{B} but we will improve this estimate.)

We may take the point of view that B_{11} and its factorization are given. In the circumstances we are considering, this also determines S_{12} and R_{12}, but it does not determine the factorization of A. Since K_{B} is known, we see that if u_{j} is the j^{th} column of S_{12} and v_{j} is the j^{th} column of S_{22}, then ∥u_{j}∥^{2} + ∥v_{j}∥^{2} ≤ K_{B} so that ∥v_{j}∥^{2} ≤ K_{B} − ∥u_{j}∥^{2}. We obtain similar inequalities for the columns of R_{22}. Thus, we want to factor A as S∗_{22}R_{22} where the columns of S_{22} and R_{22} satisfy these inequalities. For each column of S_{22}, let ϕ_{j} = (K_{B} − ∥u_{j}∥^{2})^{−1/2} and let ψ_{j} be defined similarly for each column of R_{22}. If Φ and Ψ are the diagonal matrices whose diagonal entries are the ϕ_{j} and the ψ_{j} respectively, we see that A has a factorization S∗_{22}R_{22} satisfying the inequalities for the column norms if and only if the matrix Z = ΦS∗_{22}R_{22}Ψ = ΦAΨ has a factorization Z = Ŝ∗_{22}R̂_{22} with c(Ŝ_{22}) ≤ 1 and c(R̂_{22}) ≤ 1, that is K_{Z} ≤ 1. We summarize this analysis in the following theorem.

Theorem 2.1. Suppose B is an n × n matrix with block form

( \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} )

where B_{11} is invertible, Hadamard irreducible, and K_{B_{11}} = K_{B}. If B_{11} = S∗_{11}R_{11} is a factorization with c(S_{11})^{2} = c(R_{11})^{2} = K_{B}, then B has a factorization of the form B = S∗R where K_{B} = c(S)^{2} = c(R)^{2} and

S = ( \begin{matrix}S_{11} & S_{12} \\ 0 & S_{22} \end{matrix} ) and R = ( \begin{matrix}R_{11} & R_{12} \\ 0 & R_{22} \end{matrix} )

if and only if K_{Z} ≤ 1 where Z = Φ(B_{22} −B_{21}B_{11}^{−1}B_{12})Ψ as in the preceding discussion.

Corollary 2.2. Suppose B is a non–zero n×n matrix such that b_{11} ≥ |b_{ij}| for 1 ≤ i, j ≤ n and b_{11} > |b_{1j}| and b_{11} > |b_{i1}| for 1 < i, j ≤ n. Then K_{B} = b_{11} if and only if K_{Z} ≤ 1 where

Z_{ij} = \frac{(b_{11}b_{ij} − b_{i1}b_{1j})}{\sqrt{b_{11}^{2} − b_{i1}^{2}}\sqrt{b_{11}^{2} − b_{1j}^{2}}} for i, j = 2, ⋯, n

Although we have been unable to prove that Watson’s algorithm converges to K_{B} for most starting unitaries and that the procedure above finds a factorization that shows the lower bound from Watson’s algorithm is exact, the algorithm seems to be very robust. Of course, it is easy to produce starting unitaries that are stationary points for the algorithm: for example, the identity is a stationary point for the algorithm that gives the largest diagonal entry as the lower estimate. However, we have been unable to find a matrix and non–stationary starting unitary for which Watson’s algorithm converges to a local maximum less than K_{B}.

3. WITTSTOCK’S DECOMPOSITION THEOREM

Recall that a positive semidefinite matrix B has K_{B} = max{b_{jj} : j = 1, 2, ⋯, n}. First, we show that a Hermitian matrix can be split in such a way that its multiplier norm can be easily obtained from the pieces. This result is a sharp form, for our special case, of Wittstock’s decomposition theorem [12, page 107].

Theorem 3.1. Let B be a Hermitian matrix. If P_{1} and Q_{1} are positive semidefinite matrices so that B = P_{1} −Q_{1}, then K_{B} ≤ K_{P_{1}+Q_{1}}. Moreover, there are positive semidefinite matrices P and Q so that B = P − Q and K_{B} = K_{P +Q} with rank(P) being the number of positive eigenvalues of B and rank(Q) being the number of negative eigenvalues.

The theorem says we must be concerned with the ways in which the matrix B can be split as B = P −Q where P and Q are positive semidefinite and rank(P) is the number of positive eigenvalues of B and rank(Q) is the number of negative eigenvalues of B. One such splitting is given by the spectral theorem: let P_{0} be the restriction of B to the subspace spanned by the eigenvectors corresponding to the positive eigenvalues of B and let Q_{0} be the restriction of −B to the subspace spanned by the eigenvectors corresponding to the negative eigenvalues of B. We will call this splitting the spectral splitting. That this is not the only, or always the optimal, splitting of B is what gives this theorem interest.

Proof. (of Theorem 3.1.) Assume first that B is an invertible Hermitian matrix. It follows from the Theorem and Corollary 3 of [2, pages 183 and 195] that

K_{B} = min \{K_{Z} : ( \begin{matrix}Z & B \\ B & Z \end{matrix} ) ≥ 0\}

(See [5] and [9] for discussions of this characterization.)

Suppose P_{1} and Q_{1} are positive semidefinite matrices so that B = P_{1} − Q_{1}. Then

( \begin{matrix}P_{1} + Q_{1} & P_{1} − Q_{1} \\ P_{1} − Q_{1} & P_{1} + Q_{1} \end{matrix} ) = ( \begin{matrix}P_{1} + Q_{1} & B \\ B & P_{1} + Q_{1} \end{matrix} )

is also positive semidefinite so, by the characterization above,

K_{B} ≤ K_{P_{1}+Q_{1}}

Let A be a matrix that attains the minimum above, that is, K_{A} = K_{B} and

( \begin{matrix}A & B \\ B & A \end{matrix} ) ≥ 0

The matrix C = A^{−1/2}BA^{−1/2} is an invertible Hermitian matrix with the same inertia as B. If we let C = C_{+} − C_{−} be the spectral splitting of C as a difference of positive semidefinite matrices, then P = A^{1/2}C_{+}A^{1/2} and Q = A^{1/2}C_{−}A^{1/2} are positive semidefinite matrices with P − Q = B and rank(P) and rank(Q) being the number of positive and negative eigenvalues of B. Since

( \begin{matrix}I & A^{−1/2}BA^{−1/2} \\ A^{−1/2}BA^{−1/2} & I \end{matrix} )

= ( \begin{matrix}A^{−1/2} & 0 \\ 0 & A^{−1/2} \end{matrix} ) ( \begin{matrix}A & B \\ B & A \end{matrix} ) ( \begin{matrix}A^{−1/2} & 0 \\ 0 & A^{−1/2} \end{matrix} ) ≥ 0

and C_{+}C_{−} = 0, it follows that C_{+} + C_{−} ≤ I which implies P + Q ≤ A. Thus, K_{B} ≤ K_{P +Q} ≤ K_{A} = K_{B} and P and Q satisfy the conclusion of the theorem.

Now if B is not invertible, we can find a sequence of invertible Hermitian matrices converging to B and apply the results above to each of the matrices in the sequence. Since the Hadamard multiplier norm is continuous, we can find convergent subsequences to obtain positive semidefinite matrices P and Q so that B = P − Q, K_{B} = K_{P +Q}, and rank(P) and rank(Q) are, respectively, at least as large as the number of positive and negative eigenvalues. Let N be the orthogonal projection onto the range of B. Now B = NBN = NP N − NQN and NP N and NQN are positive semidefinte matrices whose ranks are, respectively, the number of positive and negative eigenvalues of B. Since NP N + NQN ≤ P + Q, the largest diagonal entry of NP N + NQN is no more than the largest diagonal entry of P + Q and we see that K_{B} = K_{NP N+NQN}. Thus, B = NP N − NQN is a splitting of the sort needed for the conclusion.

As noted above, the spectral splitting of B is not the only splitting. To find other splittings, we consider the quadratic form ⟨Bv, v⟩, and let P = {v : ⟨Bv, v⟩ > 0} and N = {v : ⟨Bv, v⟩ < 0}. In the invertible case, if B = P − Q is a splitting and Qx = 0, then ⟨Bx, x⟩ = ⟨P x, x⟩ ≥ 0. Since rank(A) = n = rank(P) + rank(Q) and A = P + Q, only the zero vector is in the range of P and the range of Q. This means that only the zero vector is in the kernel of P and the kernel of Q. That is, if both Qx = 0 and P x = 0 then x = 0, so the non–zero x with Qx = 0 are in P. In particular, the range of Q, which is spanned by the eigenvectors of Q, is a subspace whose orthogonal complement lies in P. Similarly, the range of P, which is spanned by the eigenvectors of P, is a subspace whose orthogonal complement lies in N. The theorem below uses this observation to characterize the splittings in a special case.

Theorem 3.2. Suppose B is an n × n Hermitian matrix with n − 1 positive, one negative eigenvalue and suppose u is an eigenvector of B for which B = P_{0} −uu∗ is the spectral splitting of B. For w orthogonal to u, if α = \sqrt{1 + w∗P_{0}w}, then Q = (αu + P_{0}w)(αu + P_{0}w)∗ is a positive semidefinite matrix with rank one such that P = B + Q is a positive semidefinite matrix with rank n − 1. Conversely, if B = P − Q where P is a positive semidefinite matrix with rank n − 1 and Q is a positive semidefinite matrix with rank one, then there is a vector w orthogonal to u such that Q = (αu + P_{0}w)(αu + P_{0}w)∗ for α = \sqrt{1 + w∗P_{0}w}.

Proof. Every positive semidefinite matrix Q with rank one has the form

Q = (αu + v)(αu + v)∗

for some α ≥ 0 and some vector v orthogonal to u. If α were 0, then u would be a vector orthogonal to the range of Q that is not in P, so the remarks above show α > 0 for the desired splittings of B as P − Q. Since P_{0} has n − 1 positive eigenvalues, for every vector v orthogonal to u, there is a vector w orthogonal to u so that P_{0}w = v. Now if the scalar β and the vector x orthogonal to u are such that βu + x is orthogonal to the range of Q, then, recalling that P_{0}u = 0, we have

0 = (αu + P_{0}w)∗(βu + x) = αβ∥u∥^{2} + w∗P_{0}x

so β∥u∥^{2} = −w∗P_{0}x/α. Thus the condition that βu + x be in P is

0 < (βu + x)∗(P_{0} − uu∗)(βu + x) = x∗P_{0}x − |β|^{2}∥u∥^{4}

or

x∗P_{0}x − \frac{1}{α^{2}} x∗P_{0}ww∗P_{0}x > 0

For this to be true for every x orthogonal to u means that P_{0}−P_{0}ww∗P_{0}/α^{2} is positive definite as an operator on range(P_{0}). This is equivalent to α^{2}I − (\sqrt{P_{0}}w)(\sqrt{P_{0}}w)∗ > 0 which is the same as ∥\sqrt{P_{0}}w∥ < α.

Now suppose w, α, and Q are as in the statement of the theorem. Since

α^{2} = 1 + w∗P_{0}w > w∗P_{0}w = ∥\sqrt{P_{0}}w∥^{2}

all vectors z that are orthogonal to the range of Q are in P so z∗P z = z∗(B + Q)z = z∗Bz > 0 which implies the rank of P is at least n − 1. But

P (−\frac{α}{∥u∥^{2}} u + w)

= (P_{0} − uu∗ + (αu + P_{0}w)(αu + P_{0}w)∗) (−\frac{α}{∥u∥^{2}} u + w)
= P_{0}w + αu + (αu + P_{0}w)(−α^{2} + w∗P_{0}w)
= (αu + P_{0}w)(1 − α^{2} + w∗P_{0}w) = 0

so P has rank exactly n − 1.

To prove the converse, suppose B = P −Q is a splitting as in the theorem and Q = (αu + P_{0}w)(αu + P_{0}w)∗ for some α > 0 and w orthogonal to u. Suppose βu+x is a non–zero vector in the kernel of P where x is orthogonal to u. We have

P (βu + x) = (P_{0} − uu∗ + (αu + P_{0}w)(αu + P_{0}w)∗) (βu + x)

= P_{0}x − β∥u∥^{2}u + (αu + P_{0}w)(αβ∥u∥^{2} + w∗P_{0}x)

= ((α^{2} − 1)β∥u∥^{2} + αw∗P_{0}x) u + P_{0} (x + αβ∥u∥^{2}w + (w∗P_{0}x)w)

For this to be 0, since u is orthogonal to the range of P_{0}, we must have

(α^{2} − 1)β∥u∥^{2} + αw∗P_{0}x = 0

so

w∗P_{0}x = −(α^{2} − 1)β∥u∥^{2}/α

Moreover, since P_{0} is invertible on the set of vectors orthogonal to u, we must have

0 = x + αβ∥u∥^{2}w + (w∗P_{0}x)w
= x + (αβ∥u∥^{2} − (α^{2} − 1)β∥u∥^{2} \frac{1}{α}) w = x + \frac{β∥u∥^{2}}{α} w

Using this in the above equality, we see

−(α^{2} − 1)\frac{β∥u∥^{2}}{α} = w∗P_{0}x = −\frac{β∥u∥^{2}}{α} w∗P_{0}w

If β were 0, this would mean x = 0 and βu + x = 0, so β is non–zero and

α^{2} − 1 = w∗P_{0}w

as in the conclusion.

We can apply these ideas to get a straightforward minimization problem for the rank two case. Suppose u and v are linearly independent vectors in R^{n} and B = vv∗ − uu∗ is a Hermitian matrix. (Note that all Hermitian matrices with rank 2 for which neither B nor −B is positive semidefinite are of this form.) We need to write B = P − Q where P and Q are positive semidefinite rank one matrices with P +Q having its largest diagonal entry as small as possible. So

P = (αu + βv)(αu + βv)∗ and Q = (γu + δv)(γu + δv)∗

for some scalars α, β, γ, δ. The independence of u and v implies uu∗, uv∗, vu∗, and vv∗ are linearly independent matrices so equating vv∗ − uu∗ and P − Q gives α^{2} − γ^{2} = 1, αβ − γδ = 0, and β^{2} − δ^{2} = −1. Without loss of generality, this means

P = (αu + βv)(αu + βv)∗ and Q = (βu + αv)(βu + αv)∗

where α^{2} − β^{2} = 1 and α > 0. Now

P + Q = (α^{2} + β^{2})(vv∗ + uu∗) + 2αβ(vu∗ + uv∗)

Setting t = 2αβ, we see α^{2} + β^{2} = \sqrt{1 + t^{2}}. Thus

K_{B} = min_{t} max (diag (\sqrt{1 + t^{2}}(vv∗ + uu∗) + t(vu∗ + uv∗)))

If u_{j} and v_{j} are the j^{th} components of u and v respectively, letting f_{j}(t) = \sqrt{1 + t^{2}}(v_{j}^{2} + u_{j}^{2}) + 2tv_{j}u_{j} gives

K_{B} = min_{t} max_{j} f_{j}(t)

Since each of the f_{j} is a convex function,

K_{B} = f_{j_{0}}(t_{0})

where either f_{j_{0}} has a minimum at t_{0} and f_{j_{0}}(t_{0}) ≥ f_{j}(t_{0}) for j = 1, ⋯, n or there are i_{0} ≠ j_{0} so that f_{i_{0}}(t_{0}) = f_{j_{0}}(t_{0}) ≥ f_{j}(t_{0}) for j = 1, ⋯, n. That is, to find K_{B}, we need only check the minima of the f_{j} and the points where the graphs cross.

The values of the functions where the graphs cross do not seem to have convenient expressions, but it turns out that the minimum value of f_{j} is |b_{jj}| and the value of f_{k} at this point is (2b_{jk}^{2} − b_{kk}b_{jj})/|b_{jj}|. Since K_{B} is at least as large as |b_{jj}| for each j, we have another proof of Theorem 9 of [4] for this case.

Corollary 3.3. Let B = (b_{ij}) be a real Hermitian n × n matrix with rank 2. If b_{jj} > 0 and b_{jj} is the largest diagonal entry of B, then the following are equivalent:

(i) K_{B} = b_{jj}.

(ii) Every 2 × 2 principal submatrix containing b_{jj} has Hadamard multiplier norm b_{jj}.

(iii) For 1 ≤ k ≤ n,

b_{jj}^{2} + b_{jj}b_{kk} − 2b_{jk}^{2} ≥ 0

4. NUMERICAL RESULTS

A Matlab program FindKB that carries out Watson’s iterative algorithm, finds a factorization of the type discussed in Section 2 along with the unitaries V and W and vectors x and y, and computes upper and lower bounds for K_{B} can be obtained (cowen@math.purdue.edu) from the first author. The inputs are the matrix B whose Hadamard multiplier norm is to be found, a number of iterations to be done, and a starting unitary matrix. The lower bound for K_{B} is computed as in the description of the Watson algorithm. The upper bound c(R)c(S) for K_{B} given by Haagerup’s Theorem is computed using Equation (3) to find an S and R = (S∗)^{−1}B to find the corresponding factor R. The algorithm fails if the matrix X used in the computation of S is not invertible.

All the computations reported here were done with Matlab [10] version 4.1 on a Macintosh Quadra 950 and the starting unitary was generated by the program (by QR–factorization of a random matrix) rather than being user specified. This algorithm produces the following results for the triangular truncation matrices, that is, for the n × n matrices T for which T_{ij} = 1 when i + j ≤ n + 1 and T_{ij} = 0 when i + j > n + 1. In each case, the lower bound from Watson’s algorithm and the upper bound from the resulting factorization differ by less than 2 × 10^{−14}. The lower bound is given in the table below for K_{T} for n = 2, ⋯, 50.

One of the convenient features of the triangular truncation matrices is that the convergents computed in Watson’s algorithm give a factorization of T for which the Haagerup upper bound is essentially equal to the lower bound. We believe this happens because there are no submatrices of T with the same Hadamard multiplier norm. The same is true of McEachin’s matrices [11] the norms of some of which were computed in [5].

It might be noted that the stopping criterion written into the algorithm used by the authors is a number, Kstop, of iterations. It would be easy to modify the stopping criterion to be, for example, that the difference between two successive iterates of the lower bound be smaller than a given epsilon. Some caution needs to be exercised, however, as the various output variables converge at quite different rates. For example, in computing the Hadamard multiplier norm for the 50 × 50 triangular truncation matrix, the lower bound estimate is correct to 14 decimal places after Kstop = 60 iterations, whereas, at that point, the upper bound estimate is only correct to 7 decimal places. To get the upper bound estimate to be correct to 14 decimal places requires about Kstop = 130 iterations.

Table 1

   n         K_T                n           K_T

                             26     1.84464503202383
 2   1.15470053837925        27     1.85566122168631
 3   1.25319726474218        28     1.86629172019688
 4   1.32612266648237        29     1.87656283483510
 5   1.38423194069267        30     1.88649825965243
 6   1.43262139077559        31     1.89611941132500
 7   1.47412419160510        32     1.90544571264071
 8   1.51048356114476        33     1.91449483313437
 9   1.54285069801945        34     1.92328289442527
10   1.57202669921690        35     1.93182464630082
11   1.59859201851078        36     1.94013361841505
12   1.62298098962732        37     1.94822225154975
13   1.64552725432741        38     1.95610201165968
14   1.66649276502696        39     1.96378348934513
15   1.68608702122257        40     1.97127648693326
16   1.70448024411923        41     1.97859009497756
17   1.72181264978498        42     1.98573275968352
18   1.73820113209454        43     1.99271234252354
19   1.75374417916747        44     1.99953617310344
20   1.76852555639746        45     2.00621109617797
21   1.78261711023281        46     2.01274351357634
22   1.79608093350023        47     2.01913942168573
23   1.80897105939639        48     2.02540444504639
24   1.82133480230775        49     2.03154386653308
25   1.83321383040637        50     2.03756265453114

If the matrix X needed in the computation of S is not invertible, a multistep procedure based on Theorem 2.1 is needed. As an example of the techniques needed to handle a more complicated case, consider the following 5 × 5 matrix. The steps indicated below outline the Matlab program Multistep which can also be obtained from the first author.

 B =
    -1.6688  -0.2358   0.9445   1.1862   0.9198
     1.5766   1.9792  -1.0445   0.6810   0.1804
    -0.9223   0.7425  -2.1884   0.8284   0.3286
     0.2944   0.0148   0.9386   0.2742  -0.0324
    -0.4420   0.0872   0.2947   0.2091  -0.2410

After convergence, the lower bound for K_{B} is 2.2835 but the vectors x and y in the algorithm have zeros in their last two components, so no upper bound is computed. However, following the ideas of Theorem 2.1, we suspect the upper left 3 × 3 submatrix of B has the same Hadamard multiplier norm. Factoring this submatrix and continuing as in Theorem 2.1, we compute

   S11 =                             S12 =
      0.5259  -0.7162  -1.4586          0.5972   0.1564
      1.0427  -1.2669   0.3949         -0.1623   0.2531
     -0.9590  -0.4069   0.0091         -0.3096  -0.3919
   R11 =                             R12 =
      0.2369  -0.7355   1.5046         -0.5261  -0.1716
     -1.4669  -0.8122   0.0187          0.1852   0.2171
      0.2752  -1.0406  -0.1395         -1.3241  -0.8172
   PHI =                             PSI =
      0.7444        0                   2.1357        0
           0   0.6999                        0   0.8061

and

   Z =
      0.3315  -0.0886
     -0.4101  -0.3325

Using FindKB on this matrix, we find K_{Z} = 0.4375, which is good since Theorem 2.1 requires that K_{Z} ≤ 1 to proceed. The corresponding optimal factorization (for the upper bound from the Haagerup theorem) is

   Sz =                         Rz =
      0.4164  -0.6511             0.6509   0.4190
     -0.5140  -0.1165            -0.1177   0.5118

We now compute S_{22} and R_{22} from Sz, Rz, PHI and PSI to use in the factorization of B. In this case, we get

   S =
     0.5259  -0.7162  -1.4586   0.5972   0.1564
     1.0427  -1.2669   0.3949  -0.1623   0.2531
    -0.9590  -0.4069   0.0091  -0.3096  -0.3919
          0        0        0   0.5593  -0.9303
          0        0        0  -0.6905  -0.1665
   R =
     0.2369  -0.7355   1.5046  -0.5261  -0.1716
    -1.4668  -0.8122   0.0187   0.1852   0.2171

     0.2752  -1.0406  -0.1395  -1.3241  -0.8172
          0        0        0   0.3048   0.5199
          0        0        0  -0.0551   0.6349

It can be checked that B = S∗R and that the norms of the columns of S and R are

   cS =
     1.5111   1.5111   1.5111   1.1262   1.0655
   cR =
     1.5111   1.5111   1.5111   1.4698   1.1907

so K_{B} ≤ c(S)c(R) = 2.2835 which agrees with lower bound found earlier.

Although, as we noted above, we have been unable to prove that the algorithm always works, it is self checking; that is, if the upper and lower bound estimate of K_{B} are acceptably close, we know the algorithm has worked in this case. In a typical problem, one would apply FindKB to a matrix. If the upper and lower estimates of the Hadamard multiplier norm are significantly different, then the non–zero components of x and y indicate the rows and columns, respectively, of the matrix that comprise the important submatrix B̂. Then, Multistep can be used to find the resulting factorization and upper bound estimate of B̂. If the lower right corner produced by the algorithm is also Hadamard reducible, the process must be iterated to find the eventual factorization.

Our experience is that Watson’s algorithm is quite robust. In addition to the structured triangular truncation and McEachin matrices, we generated 165 random 10×10 matrices using Matlab’s randn(10,10) command; that is, the entries of the matrices were chosen from a normal distribution with mean 0 and standard deviation 1. In each case, the Watson algorithm converged to what was shown by the subsequent upper bound estimates to be the Hadamard multiplier norm of the matrix. Random starting unitaries were used and 500 iterations of the algorithm were sufficient to give agreement of the upper and lower estimates for K_{B} of 7 to 14 decimal places in the Hadamard irreducible cases. (Watson’s algorithm converges much faster than that to the lower bound estimate, but a large number of iterations are required to get a factorization that gives an acceptably small upper bound.) Of the 165 cases, 90 matrices were Hadamard irreducible, 37 had a 9×9 submatrix with the same Hadamard multiplier norm, 12 had an 8 × 8 submatrix, 1 each had 7 × 7, 6 × 6, and 5 × 5 submatrices, 5 had 2 × 2 submatrices, and in 18 cases the Hadamard multiplier norm was the absolute value of the largest entry, i.e. a 1 × 1 submatrix.

REFERENCES

1 T. Ando, R. A. Horn, and C. R. Johnson, The singular values of

a Hadamard product: a basic inequality, Linear Multilinear Alg. 21:345– 365(1987).

2 T. Ando and K. Okubo, Induced norms of the Schur multiplier operator, Linear Alg. Appl. 147:181–199(1991).

3 J. R. Angelos, C. C. Cowen, and S. K. Narayan, Triangular trun-

cation and finding the norm of a Hadamard multiplier, Linear Alg. Appl. 170:117–135(1992).

4 C. C. Cowen, K. E. Debro, and P. D. Sepanski, Geometry and the

norms of Hadamard multipliers, Linear Alg. Appl., to appear.

5 C. C. Cowen, M. A. Dritschel, and R. C. Penney, Norms of

Hadamard multipliers, SIAM J. Matrix Anal. Appl. 15:313–320(1994).

6 U. Haagerup, Decompositions of completely bounded maps on operator algebras, preprint.

7 R. A. Horn, The Hadamard product, Proc. Symposia Appl. Math.

40:87–169(1990).

8 R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.

9 R. Mathias, Matrix completions, norms and Hadamard products,

Proc. Amer. Math. Soc. 117:905–918(1993).

10 The MathWorks, MATLAB, Version 4.1, The MathWorks, South Natick, Massachusetts, 1993.

11 R. V. McEachin, A sharp estimate for an operator inequality,

Proc. Amer. Math. Soc. 115:161–165(1992).

12 V. I. Paulsen, Completely Bounded Maps and Dilations, Pitman Research Notes in Mathematics #146, Wiley, New York, 1986.

13 V. I. Paulsen, S. C. Power, and R. R. Smith, Schur products and

matrix completions, J. Functional Analysis 85:151–178(1989).

14 I. Schur, Bemerkungen zur theorie de beschränkten bilinearformen mit unendlich vielen veränderlichen, J. reine angew. Math. 140:1–28(1911).

15 G. A. Watson, Estimating Hadamard multiplier norms, with application to triangular truncation, Linear Alg. Appl., to appear.