Remarks on the Unitary Triangularization of a Nonsymmetric Matrix

ABSTRACT

In [1], A. Householder described a method for the unitary triangularization of a matrix. The formulas given there are valid for the real case. In this note we describe the modifications to handle the complex case and also point out a small modification in the real case which will improve the numerical accuracy of the method. At first we are concerned with a complex vector space. The basic tool is the fact that if ‖ u ‖ = √2, then the matrix I - uu* is unitary, as may be readily verified. The following lemma is a modification of the one give in [1]. LEMMA. Let a ≠ 0 be an arbitrary vector and let v be an arbitrary unit vector. Then there exists a vector u with ‖ u ‖ = √2 and a scalar &zgr; with | &zgr; | = 1 such that (I - uu*)a = &zgr; ‖ a ‖ v. (1) PROOF: Letting &agr; = ‖ a ‖ and &mgr; = u*a, (1) may be written a - &agr;&zgr;v = &mgr;u. (2) Multiply by a* gives &agr;2 - &agr;&zgr;a*v = &mgr;a*u = ‖ &mgr; ‖2. (3) It follows that &zgr;a*v is real. Assuming for the moment that a*v ≠ 0, we write it in polar form a*v = rw, r > 0, ‖ w ‖ = 1. Then the fact that &zgr;rw is real implies that &zgr; = ± w. (4) Substituting into (3) gives ‖ &mgr; ‖2 = &agr;2 ∓ &agr;r. (5) We now set, arbitrarily, arg (&mgr;) = 0. Then &mgr; = √&agr;(&agr; ∓ r). (6) Next, we select the negative sign in (4) in order to avoid the subtraction of two positive quantities in (6), since such a subtraction may give rise to numerical difficulties. Collecting the formulas, we see that the following sequence of computations will produce the required u and &zgr;: &agr; = ‖ a ‖ (7) r = ‖ a*v ‖ (8) &zgr; = -a*v/r (9) &mgr; = √ &agr;(&agr; + r) (10) u = 1/&mgr;(a - &zgr;&agr;v). (11) The case a*v = 0 may be handled if, instead of using (9), we let &zgr; be an arbitrary number with ‖ &zgr; ‖ = 1. It is easily verified that the formulas thus modified will still work. The computation requires 3 square roots to compare &agr;, r, and &mgr;. A slight modification [1] permits one to avoid the root required to compute &mgr;. In the real case, no root is required to compute r. Now consider the case of a real vector space. The formulas given [1] for this case are essentially the same as ours except that (8) is replaced by r = a*v, and (10) by &mgr; = √&agr;(&agr; - r). If &mgr; is computed this way and if r is positive and near &agr; (as is the case when v is near a/&agr;), cancellation of significant digits will occur. This difficulty, and the need for making a special case when v is exactly a/&agr;, is avoided in the present set of formulas.

REFERENCES

• 1: Alston S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, Journal of the ACM (JACM), v.5 n.4, p.339-342, Oct. 1958 [doi>10.1145/320941.320947]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Theory, Verification