Perturbation bounds for the Cholesky andQR factorizations

LetA, A+E be Hermitian positive definite matrices. Suppose thatA=LL ^H andA+E=(L+G)(L+G)^H are the Cholesky factorizations ofA andA+E, respectively. In this paper lower bounds and upper bounds on |G|/|L| in terms of |E|/|A| are given. Moreover, perturbation bounds are given for the QR factorization of a complexm ×n matrixA of rankn.This research was supported by the National Science Foundation of China and the Department of Mathematics of Linköping University in Sweden.     

Derived equivalence of algebras

The derived equivalence and stable equivalence of algebrasR _A ^m and R _B ^m are studied. It is proved, using the tilting complex, thatR _A ^m andR _B ^m are derived-equivalent whenever algebrasA andB are derived-equivalent.     

Approximate factorizations with S/P consistently ordered M-factors

The behaviour of PCG methods for solving a finite difference or finite element positive definite linear systemAx=b with a (pre)conditioning matrixB=U ^TP^–1 U (whereU is upper triangular andP=diag(U)) obtained from a modified incomplete factorization, isunpredictable in the present status of knowledge whenever the upper triangular factor is not strictly diagonally dominant and 2P –D, whereD=diag(A), is not symmetric positive definite. The origin of this rather surprising shortcoming of the theory is that all upper bounds on the associated spectral condition number (B ^–1 A) obtained so far require either the strict diagonal dominance of the upper triangular factor or the strict positive definiteness of 2P –D. It is our purpose here to improve the theory in this respect by showing that, when the triangular factors are S/P consistently orderedM-matrices, nonstrict diagonal dominance is generally a sufficient requirement, without additional condition on 2P –D. As a consequence, the new analysis does not require diagonal perturbations (otherwise needed to keep control of the diagonal dominance ofU or of the positive definiteness of 2P –D). Further, the bounds obtained here on (B ^–1 A) are independent of the lower spectral bound ofD ^–1 A meaning that quasi-singular problems can be solved at the same speed as regular ones, an unexpected result.     

A graph theoretic approach to matrix inversion by partitioning

LetM be a square matrix whose entries are in some field. Our object is to find a permutation matrixP such thatPM P ^–1 is completely reduced, i.e., is partitioned in block triangular form, so that all submatrices below its diagonal are 0 and all diagonal submatrices are square and irreducible. LetA be the binary (0, 1) matrix obtained fromM by preserving the 0's ofM and replacing the nonzero entries ofM by 1's. ThenA may be regarded as the adjacency matrix of a directed graphD. CallD strongly connected orstrong if any two points ofD are mutually reachable by directed paths. Astrong component ofD is a maximal strong subgraph. Thecondensation D ^* ofD is that digraph whose points are the strong components ofD and whose lines are induced by those ofD. By known methods, we constructD ^* from the digraph,D whose adjacency matrixA was obtained from the original matrixM. LetA ^* be the adjacency matrix ofD ^*. It is easy to show that there exists a permutation matrixQ such thatQA ^* Q ^–1 is an upper triangular matrix. The determination of an appropriate permutation matrixP from this matrixQ is straightforward.This was an informal talk at the International Symposium on Matrix Computation sponsored by SIAM and held in Gatlinburg, Tennessee, April 24–28, 1961 and was an invited address at the SIAM meeting in Stillwater, Oklahoma on August 31, 1961     

On the Cholesky factorization of the Gram matrix of locally supported functions

Cholesky factorization of bi-infinite and semi-infinite matrices is studied and in particular the following is proved. If a bi-infinite matrixA has a Cholesky factorization whose lower triangular factorL and its lower triangular inverse decay exponentially away from the diagonal, then the semi-infinite truncation ofA has a lower triangular Cholesky factor whose elements approach those ofL exponentially. This result is then applied to studying the asymptotic behavior of splines obtained by orthogonalizing a large finite set of B-splines, in particular identifying the limiting profile when the knots are equally spaced.The first and second authors were partially supported by Nato Grant #920209, the second author also by the Alexander von Humboldt Foundation, and the last two authors by the Italian Ministry of University and Scientific and Technological Research.     

Deadbeat control: A special inverse eigenvalue problem

In this paper we give a numerical method to construct a rankm correctionBF (where then ×m matrixB is known and them ×n matrixF is to be found) to an ×n matrixA, in order to put all the eigenvalues ofA +BF at zero. This problem is known in the control literature as deadbeat control. Our method constructs, in a recursive manner, a unitary transformation yielding a coordinate system in which the matrixF is computed by merely solving a set of linear equations. Moreover, in this coordinate system one easily constructs the minimum norm solution to the problem. The coordinate system is related to the Krylov sequenceA ^–1 B,A ^–2 B,A ^–3 B, .... Partial results of numerical stability are also obtained.Dedicated to Professor Germund Dahlquist: on the occasion of his 60th birthday     

Separability of distinct Boolean rank-1 matrices

For two distinct rank-1 matricesA andB, a rank-1 matrixC is called aseparating matrix ofA andB if the rank ofA+C is 2 but the rank ofB+C is 1 or vice versa. In this case, rank-1 matricesA andB are said to beseparable. We show that every pair of distinct Boolean rank-1 matrices are separable.     

Necessary and sufficient condition in Lyapunov robust control: Multi-input case

We consider a linear time-invariant finite-dimensional system x=Ax+Bu with multi-inputu, in which the matricesA andB are in canonical controller form. We assume that the system is controllable andB has rankm. We study the Lyapunov equationPA+A ^T P+Q=0, withQ>0, and investigate the properties thatP must satisfy in order that the canonical controller matrixA be Hurwitz. We show that, for the matrixA being Hurwitz, it is necessary and sufficient thatB ^T PB>0 and that the determinant ofB ^T PW be Hurwitz, whereW=block diag[w ₁,...,w _m ], with elementw _i =[s ^k _i –1,s ^k _i –2,...,s, 1] ^T ; here, the symbolsk _i ,i=1, 2, ...,m, denote the Kronecker invariants with respect to the pair {A, B}. This result has application in designing robust controllers for linear uncertain systems.     

Traces of Eichler—Brandt matrices and type numbers of quaternion orders

LetA be a totally definite quaternion algebra over a totally real algebraic number fieldF andM be the ring of algebraic integers ofF. For anyM-orderG ofA we derive formulas for the massm(G) and the type numbert(G) of G and for the trace of the Eichler-Brandt matrixB(G, J) ofG and any integral idealJ ofM in terms of genus invariants ofG and of invariants ofF andJ. Applications to class numbers of quaternion orders and of ternary quadratic forms are indicated.     

Classification of Bott towers by matrix

A criterion for the classification of Bott towers is presented, i.e., two Bott towers B _*(A) and B _*(A′) are isomorphic if and only if the matrices A and A′ are equivalent. The equivalence relation is defined by two operations on matrices. And it is based on the observation that any Bott tower B _*(A) is uniquely determined by its structure matrix A, which is a strictly upper triangular integer matrix. The classification of Bott towers is closely related to the cohomological rigidity problem for both Bott towers and Bott manifolds.     

A pre-hilbert space consisting of classes of convex sets

An equivalence relation is defined in the set of all bounded closed convex sets in Euclidean spaceE ⁿ. The equivalence classes are shown to be elements of a pre-Hilbert spaceA ⁿ, and geometrical relationships betweenA ⁿ andE ⁿ are investigated.     

Group rings over Dedekind rings

Seghal posed the following question: IfA andB are rings, doesA[X,X ⁻¹] ℞B[X,X ⁻¹] implyA ℞B. In general the answer to this question is no. In this note we give an affirmative answer in the case thatA andB are Dedekind rings. The author is research assistant at the NFWO.     

On intertwining operators

LetB(H) denote the algebra of operators on the Hilbert spaceH into itself. GivenA,BB(H), defineC (A, B) andR (A, B):B(H)B(H) byC (A, B) X=AX–XB andR(A, B) X=AXB–X. Our purpose in this note is a twofold one. we show firstly that ifA andB ^*B (H) are dominant operators such that the pure part ofB has non-trivial kernel, thenC ⁿ (A, B) X=0, n some natural number, implies thatC (A, B)X=C(A ^*,B ^*)X=0. Secondly, it is shown that ifA andB ^* are contractions withC ₀ completely non-unitary parts, thenR ⁿ (A, B) X=0 for some natural numbern implies thatR (A, B) X=R (A ^*,B ^*)X=C (A, B ^*)X=C (A ^*,B) X=0. In the particular case in whichX is of the Hilbert—Schmidt class, it is shown that his result extends to all contractionsA andB.     

Hilbertian Versus Hilbert W*-Modules and Applications to L2- and other invariants

Hilbert(ian) A-modules over finite von Neumann algebras with a faithful normal trace state (from global analysis) and Hilbert W*-modules over A (from operator algebra theory) are compared and a categorical equivalence is established. The correspondence between these two structures sheds new light on basic results in L ²-invariant theory providing alternative proofs. We indicate new invariants for finitely generated projective B-modules, where B is a unital C*-algebra (usually the full group C*-algebra C*() of the fundamental group =₁(M) of a manifold M).     

The Spectral Shift Function for Certain Block Operator Matrices

Let L₀ be a 2 × 2 diagonal self‐adjoint block operator matrix with entries A and D. If operators B and B* are added to the off diagonal zeros, certain parts of the spectrum of L₀ move to the right and other parts move to the left. In this paper it is shown that, correspondingly, if B is a trace class operator M. G. Krein's spectral shift function is of constant sign on certain intervals.     

Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

Some more primitive group rings

In this paper, we show that the group rings of several families of groups are primitive. LetA andB be two groups with 1<|A|≦|B| andB infinite. Then the main result is that ifK is a field for whichK[A ^ω] is semiprimitive, thenK[A∫B] is primitive. In addition, the field may be replaced by a subdomian in caseA is not torsion orA is not locally finite andK has characteristic 0. Certain other wreath products and free products are discussed. Partially supported by the N.S.F.     

Quantum homogeneous spaces with faithfully flat module structures

LetA be a Hopf algebra with bijective antipode andB⊃A a right coideal subalgebra ofA. Formally, the inclusionB⊃A defines a quotient mapG→X whereG is a quantum group andX a right homogeneousG-space. From an algebraic point of view theG-spaceX only has good properties ifA is left (or right) faithfully flat as a module overB. In the last few years many interesting examples of quantumG-spaces for concrete quantum groupsG have been constructured by Podleś, Noumi, Dijkhuizen and others (as analogs of classical compact symmetric spaces). In these examplesB consists of infinitesimal invariants of the function algebraA of the quantum group. As a consequence of a general theorem we show that in all these casesA as a left or rightB-module is faithfully flat. Moreover, the coalgebraA/AB ⁺ is cosemisimple.