Abstract
This short note proves that if \(A\) is accretive-dissipative, then the growth factor for such \(A\) in Gaussian elimination is less than \(4\). If \(A\) is a Higham matrix, i.e., the accretive-dissipative matrix \(A\) is complex symmetric, then the growth factor is less than \(2\sqrt{2}\). The result obtained improves those of George et al. in [Numer. Linear Algebra Appl. 9, 107–114 (2002)] and is one step closer to the final solution of Higham’s conjecture.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \(\mathbb{M }_{n}(\mathbf C )\) be the set of \(n\times n\) complex matrices. For any \(A=(a_{ij})\in \mathbb{M }_n(\mathbf C )\), \(A^*\) stands for the conjugate transpose of \(A\). Similarly, \(x^*\) means the conjugate transpose of \(x\) for any \(x\in \mathbf C ^n\). \(A\in \mathbb{M }_{n}(\mathbf C )\) is accretive-dissipative if it can be written as \(A=B+iC\), where \(B=\frac{A+A^*}{2}\) and \(C=\frac{A-A^*}{2i}\) are both (Hermitian) positive definite. If \(B, C\) are real symmetric positive definite, then \(A\) is called a Higham matrix.Footnote 1
Consider the linear system
and let \(A^{(k)} =(a^{(k)}_{ij})\) be the matrix resulted from applying the first \(k\) (\(1\le k\le n-1\)) steps of Gaussian elimination to \(A\). The quantity
is called the growth factor (in Gaussian elimination) of \(A\). For more information on the numerical significance of investigating growth factor and its connection with the stability of Gaussian elimination, we refer to [3] and references threrein. It is proved in [3] that if \(A\) in (1) is a Higham matrix, then no pivoting is needed in Gaussian elimination. Higham [3] also conjectured that \(\rho _n(A)\le 2\) for such a matrix.
George et al. [2] made some progress concerning this conjecture. They obtained the following result:
Theorem 1.
Let \(A\in \mathbb{M }_{n}(\mathbf C )\) be accretive-dissipative. Then \(\rho _n(A)< 3\sqrt{2}\). If \(A\) is a Higham matrix, then \(\rho _n(A)< 3\).
They proved Theorem 1 via a stronger result, viz,
Theorem 2.
Let \(A\in \mathbb{M }_{n}(\mathbf C )\) be accretive-dissipative. Then
2 The Main Theorem
In this article, we show a tighter bound than (2). As a result, Theorem 1 is improved. Our result can be read as follows:
Theorem 3.
Let \(A\in \mathbb{M }_{n}(\mathbf C )\) be accretive-dissipative. Then
Consequently, \(\rho _n(A)< 4\). If \(A\) is a Higham matrix, then \(\rho _n(A)< 2\sqrt{2}\).
proof
Readers are assumed to have read [2]. The first few steps are the same as the proof in [2], so we skip them. We start from \(a_{jj}=b_{jj}+ic_{jj}\) and the fact that \(b_{jj}, c_{jj}>0\).
Setting
then we have
and
where
with
positive definite. It is known that \(\beta ,\gamma >0\).
By the Cauchy-Schwarz inequality and the arithmetic mean-geometric mean inequality, we have
From (4) and (5) we have [2, Lemma 2.3]
where the inequality is in the sense of Loewner partial order. Also from (6), we know
Compute
This completes the proof of (3). To show the remaining claims, we need the following facts:
Fact 1. [2, Corollary 2.3] The property of being an accretive-dissipative matrix is hereditary under Gaussian elimination.
Fact 2. [2, Lemma 2.1, 2.2] If \(A=(a_{lj})\in \mathbb{M }_{n}(\mathbf C )\) is accretive-dissipative, then \(\sqrt{2}\max \limits _{l}|a_{ll}|\ge \max \limits _{l\ne j}|a_{lj}|\). If \(A\) is a Higham matrix, then \( \max \limits _{l}|a_{ll}|\ge \max \limits _{l,j}|a_{lj}|\).
Suppose \(\max _{j,k}|a_{jj}^{(k)}|=|a_{j_0j_0}^{(k_0)}|\) for some \(j_0, k_0\), then
Similarly, we can show that if \(A\) is a Higham matrix, then \(\rho _n(A)<2\sqrt{2}\). The proof is thus complete. \(\square \)
We remark that Fact 2 in the preceding proof has been extended to norm inequalities for accretive-dissipative operator matrices; see [4].
3 Conclusion
Compared with Theorems 1 and 2, it might look minor to improve the upper bound from \(3\) to \(2\sqrt{2}\), but it is one step closer to the final solution of Higham’s conjecture. Moreover, the approach in the previous proof may also apply to other related results; see e.g. [1]. In [5], we have used a similar idea to improve a result on Fischer type determinantal inequalities for accretive-dissipative matrices.
Notes
In [2], accretive-dissipative matrix is called generalized Higham matrix.
References
George, A., Ikramov, Kh.D.: On the growth factor in Gaussian elimination for matrices with sharp angular field of values. Calcolo 41, 27–36 (2004)
George, A., Ikramov, Kh.D., Kucherov, A.B.: On the growth factor in Gaussian elimination for generalized Higham matrices. Numer. Linear Algebra Appl. 9, 107–114 (2002)
Higham, N.J.: Factorizing complex symmetric matrices with positive real and imaginary parts. Math. Comp. 67, 1591–1599 (1998)
Lin, M., Zhou, D.: Norm inequalities for accretive-dissipative operator matrices. J. Math. Anal. Appl. (2013, to appear)
Lin, M.: Fischer type determinantal inequalities for accretive-dissipative matrices. Linear Algebra Appl. 438, 2808–2812 (2013)
Acknowledgments
The author thanks Prof. Henry Wolkowicz for valuable discussion on a draft of this paper, and both referees for their comments on the presentation of the submitted version.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lin, M. A note on the growth factor in Gaussian elimination for accretive-dissipative matrices. Calcolo 51, 363–366 (2014). https://doi.org/10.1007/s10092-013-0089-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10092-013-0089-1