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     

Sign patterns that require almost unique rank

A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, −, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B:sgn(B)=A}. The minimum rank mr(A) (maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A) = mr(A) + 1, are established and are extended to sign patterns A for which the spread is d=MR(A)-mr(A). A complete characterization of the sign patterns that require almost unique rank is obtained.     

Perturbation analysis of the orthogonal procrustes problem

Given two arbitrary real matricesA andB of the same size, the orthogonal Procrustes problem is to find an orthogonal matrixM such that the Frobenius norm MA – B is minimized. This paper treats the common case when the orthogonal matrixM is required to have a positive determinant. The stability of the problem is studied and supremum results for the perturbation bounds are derived.     

On the Bartels—Golub decomposition for linear programming bases

Many implementations of the simplex method require the row of the inverse of the basis matrixB corresponding to the pivot row at each iteration for updating either a pricing vector or the nonbasic reduced costs. In this note we show that if the Bartels—Golub algorithm [1, 2] or one of its variants is used to update theLU factorization ofB, then less computing is needed if one works with the factors of the updatedB than with those ofB. These results are discussed as they apply to the column selection algorithms recently proposed by Goldfarb and Reid [4, 5] and Harris [6].This research was supported in part by the National Science Foundation under Grant GJ 36472.     

A direct method for the general solution of a system of linear equations

A computationally stable method for the general solution of a system of linear equations is given. The system isA ^Tx–B=0, where then-vectorx is unknown and then×q matrixA and theq-vectorB are known. It is assumed that the matrixA ^T and the augmented matrix [A ^T,B] are of the same rankm, wheremn, so that the system is consistent and solvable. Whenm<n, the method yields the minimum modulus solutionx _m and a symmetricn ×n matrixH _m of rankn–m, so thatx=x _m+H _my satisfies the system for ally, ann-vector. Whenm=n, the matrixH _m reduces to zero andx _m becomes the unique solution of the system.The method is also suitable for the solution of a determined system ofn linear equations. When then×n coefficient matrix is ill-conditioned, the method can produce a good solution, while the commonly used elimination method fails.This research was supported by the National Science Foundation, Grant No. GP-41158.     

A numerical procedure for computing the Moore-Penrose inverse

An algorithm for computing the Moore-Penrose inverse of an arbitraryn×m real matrixA is presented which uses a Gram-Schmidt like procedure to form anA-orthogonal set of vectors which span the subspace perpendicular to the kernel ofA. This one procedure will work for any value ofn andm, and for any value of rank (A).     

A note on the computation of an orthonormal basis for the null space of a matrix

A highly regarded method to obtain an orthonormal basis,Z, for the null space of a matrixA ^T is theQR decomposition ofA, whereQ is the product of Householder matrices. In several optimization contextsA(x) varies continuously withx and it is desirable thatZ(x) vary continuously also. In this note we demonstrate that thestandard implementation of theQR decomposition doesnot yield an orthonormal basisZ(x) whose elements vary continuously withx. We suggest three possible remedies. Work supported in part by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Applications of shortest path algorithms to matrix scalings

Summary A symmetric scaling of a nonnegative, square matrixA is a matrixXAX ^–1, whereX is a nonsingular, nonnegative diagonal matrix. By associating a family of weighted directed graphs with the matrixA we are able to adapt the shortest path algorithms to compute an optimal scaling ofA, where we call a symmetric scalingA ofA optimal if it minimizes the maximum of the ratio of non-zero elements.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthdayThe first author was partially supported by the Deutsche Forschungsgemeinschaft under grant GO 270/3, the second author by the U.S. National Science Foundation under grand MCS-8026132     

On the effective computation of the inertia of a non-hermitian matrix

Summary given a complex lower Hessenberg matrixA with unit codiagonal, a hermitian matrixH is constructed such that, ifH is non-singular InA= InH. IfA is real,H is real symmetric. Classical results of Fujiwara on the root-separation problem and of Schwarz on the eigenvalue-separation problem are included as special cases.The authors' research was conducted at the Universidade Estadual de Campinas and supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo, Brasil, under grant n⁰ 78/0490.     

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.     

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.     

Matrix completion problems of block type

The solvability, either unconditional or under certain conditions, is proved for three matrix completion problems of block type. Being a problem of block type means that a matrixA must be constructed with a prescribed characteristic polynomial and one or several blocks in a 2 × 2 partition also prescribed. For the problems under analysis, one prescribes, respectively, (a) the blockA ₁₂; (b) the blockA ₁₁; (c) the blocksA ₁₁ andA ₁₂. We discuss our experience in implementing the algorithms that solve the problems above as procedures in the symbolic computation system MAPLE. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 863–873, June, 2000. The first author was supported by the Russian Foundation for Basic Research under grant No. 97-01-00927.     

A classification of upper equivalent matrices the generic case

Two square matricesA andB are called upper equivalent iff there exists an invertible lower triangular matrixL such thatL ^–1 AL andB have the same upper triangular parts. In this paper we obtain a set of invariants for this equivalence relation. In the case when any minor of a matrixA, in the intersection of its last columns and first rows and contained in its upper triangular part is different from zero, it is shown that the above mentioned set of invariants completely determines the upper triangular parts of the matrices from the equivalence class ofA. Simple representatives for this class are also given.     

A Problem in Linear Matrix Approximation

Let A be a normal operator in ??(H), H a complex Hilbert space, and let ? _A = ? {AX - XA:X ∈ ??(H)} be the commutator subspace of ??(H) associated with A. If B in ??(H) commutes with A, then B is orthogonal to ?_A with respect to the spectral norm; i.e., the null operator is an element of best approximation of B in ? _A. This was proved by J. Anderson in 1973 and extended by P. J. Maher with respect to the Schatten p-norm recently. We take a look at their result from a more approximation theoretical point of view in the finite dimensional setting; in particular, we characterize all elements of best approximation of B in R_A and prove that the metric projection of H onto ?_A is continuous.     

Structural properties and decomposition of linear balanced matrices

Claude Berge defines a (0, 1) matrix A to be linear ifA does not contain a 2 × 2 submatrix of all ones.A(0, 1) matrixA is balanced ifA does not contain a square submatrix of odd order with two ones per row and column.The contraction of a rowi of a matrix consists of the removal of rowi and all the columns that have a 1 in the entry corresponding to rowi. In this paper we show that if a linear balanced matrixA does not belong to a subclass of totally unimodular matrices, thenA orA ^T contains a rowi such that the submatrix obtained by contracting rowi has a block-diagonal structure.Partial support from NSF grant DMS 8606188, ECS 8800281 and DDM 8800281.     

Branchings in rooted graphs and the diameter of greedoids

LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr ²–r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2^r–1.     

The vertex separator problem: a polyhedral investigation

The vertex separator (VS) problem in a graph G=(V,E) asks for a partition of V into nonempty subsets A, B, C such that there is no edge between A and B, and |C| is minimized subject to a bound on max{|A|,|B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Necessary and sufficient conditions are given for the VSP to be full dimensional. Central to our investigation is the relationship between separators and dominators. Several classes of valid inequalities are investigated, along with the conditions under which they are facet defining for the VSP. Some of our proofs combine in new ways projection with lifting.In a companion paper we develop a branch-and-cut algorithm for the (VS) problem based on the inequalities discussed here, and report on computational experience with a wide variety of (VS) problems drawn from the literature and inspired by various applications.Research supported by the National Science Foundation through grant #DMI-0098427 and by the Office of Naval Research through contract N00014-97-1-0196Research supported by the Brazilian agencies FAPESP (grant 01/14205–6), CAPES (grant BEX 04444/02–2) and CNPq (grants 302588/02–7 and Pronex 664107/97–4)     

Products of nilpotent matrices

We show that any complex singular square matrix T is a product of two nilpotent matrices A and B with rank A = rank B = rank T except when T is a 2×2 nilpotent matrix of rank one.