More refined enumerations of alternating sign matrices

We study a further refinement of the standard refined enumeration of alternating sign matrices (ASMs) according to their first two rows instead of just the first row, and more general “d-refined” enumerations of ASMs according to the first d rows. For the doubly-refined case of d=2, we derive a system of linear equations satisfied by the doubly-refined enumeration numbers A_n,i,j that enumerate such matrices. We give a conjectural explicit formula for A_n,i,j and formulate several other conjectures about the sufficiency of the linear equations to determine the A_n,i,j's and about an extension of the linear equations to the general d-refined enumerations.     

Matrix realizations of littlewood—richardson sequences

In this paper we consider the problem of characterizing the invariant factors of three matrices A B, and C, such that AB — C Our matrices have entries over a principal ideal domain or over a local domain. In Section 2 we show that this problem is localizablc

The above problem lias a well-known solution in terms of Littlewood-Richardson sequences. We introduce the concept of a matrix realization of a Littlewood-Richardson sequence. The main result is an explicit construction of a sequence of matrices which realizes a previously given Littlewood Richardson sequence. Our methods offer a matrix theoretical proof of a well-known result of T, Klein on extensions of p-modules.     

Complexity of additive computations of systems of linear forms

The additive computation of a system of linear forms can be represented by a sequence of square matrices Q₁,...,Q_T (Q_i equals the identity matrix increased or decreased by 1 in one entry). The complexity of the additive computation is the minimal number of matrices in such a representation. A connection between the additive complexity of a system with coefficient matrix A and of a system with coefficient matrix A^T is proved.     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

On the existence of convex decompositions of partially separable functions

The concept of a partially separable functionf developed in [4] is generalized to include all functionsf that can be expressed as a finite sum of element functionsf _i whose Hessians have nontrivial nullspacesN _i , Such functions can be efficiently minimized by the partitioned variable metric methods described in [5], provided that each element functionf _i is convex. If this condition is not satisfied, we attempt toconvexify the given decomposition by shifting quadratic terms among the originalf _i such that the resulting modified element functions are at least locally convex. To avoid tests on the numerical value of the Hessian, we study the totally convex case where all locally convexf with the separability structureN _i ¹ have a convex decomposition. It is shown that total convexity only depends on the associated linear conditions on the Hessian matrix. In the sparse case, when eachN _i is spanned by Cartesian basis vectors, it is shown that a sparsity pattern corresponds to a totally convex structure if and only if it allows a (permuted) LDL^T factorization without fill-in.     

Banded matrices with banded inverses,II: Locally finite decomposition of spline spaces

Given two function spacesV ₀,V ₁ with compactly supported basis functionsC _i, F_i, i∈Z, respectively, such thatC _i can be written as a finite linear combination of theF _i's, we study the problem of decomposingV ₁ into a direct sum ofV ₀ and some subspaceW ofV ₁ in such a way thatW is spanned by compactly supported functions and that eachF _i can be written as a finite linear combination of the basis functions inV ₀ andW. The problem of finding such locally finite decompositions is shown to be equivalent to solving certain matrix equations involving two-slanted matrices. These relations may be reinterpreted in terms of banded matrices possessing banded inverses. Our approach to solving the matrix equations is based on factorization techniques which work under certain conditions on minors. In particular, we apply these results to univariate splines with arbitrary knot sequences.     

Gliding hump properties of matrix domains

Gliding hump properties play an important role in numerous topics in analysis, for instance, they are used as a substitute for the uniform boundedness principle. Since examples of sequence spaces having certain gliding hump properties are rare, the main aim of this paper is to present classes of infinite matrices A such that the matrix domain E _A has a certain gliding hump property whenever a given sequence space E has this property.     

Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

Function of a square matrix with repeated eigenvalues

An analytical function f(A) of an arbitrary n×n constant matrix A is determined and expressed by the “fundamental formula”, the linear combination of constituent matrices. The constituent matrices Z_kh, which depend on A but not on the function f(s), are computed from the given matrix A, that may have repeated eigenvalues. The associated companion matrix C and Jordan matrix J are then expressed when all the eigenvalues with multiplicities are known. Several other related matrices, such as Vandermonde matrix V, modal matrix W, Krylov matrix K and their inverses, are also derived and depicted as in a 2-D or 3-D mapping diagram. The constituent matrices Z_kh of A are thus obtained by these matrices through similarity matrix transformations. Alternatively, efficient and direct approaches for Z_kh can be found by the linear combination of matrices, that may be further simplified by writing them in “super column matrix” forms. Finally, a typical example is provided to show the merit of several approaches for the constituent matrices of a given matrix A.     

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.     

Pentadiagonal Oscillatory Matrices with Two Spectrum in Common

We denote the spectrum of an square matrix A by σ(A), and that of the matrix obtained by deleting the first i rows and columns of A by σ_i(A). It is known that a symmetric pentadiagonal oscillatory (SPO) matrix may be constructed from σ, σ₁ and σ₂. The pairs σ, σ₁ and σ₁, σ₂ must interlace; the construction is not unique; and the conditions on the data which ensure that A is oscillatory are extremely complicated. Given one SPO matrix A, the paper shows that operations may be applied to A to construct a family of such matrices with σ and σ₁ in common. Moreover, given one totally positive (TP) matrix A, we construct a family of TP matrices with σ, σ₁ and σ₂ in common.     

On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruences

Let {A_i }and {B_i } be two given families of n-by-n matrices. We give conditions under which there is a unitary U such that every matrix UA_iU ¹ is upper triangular. We give conditions, weaker than the classical conditions of commutativity of the whole family, under which there is a unitary U such that every matrix UA_jU ^? is upper triangular. We also give conditions under which there is one single unitary U such that every UA_iU ¹ and every UB_jU ^? is upper triangular. We give necessary and sufficient conditions for simultaneous unitary reduction to diagonal form in this way when all the A_j's are complex symmetric and all theB_j 's are Hermitian.     

The characteristic polynomial of a principal subpencil of a Hermitian matrix pencil

Given n-square Hermitian matrices A,B, let A_i,B_i denote the principal (n?1)- square submatrices of A,B, respectively, obtained by deleting row i and column i. Let μ, λ be independent indeterminates. The first main result of this paper is the characterization (for fixed i) of the polynomials representable as det(μA_i?λB_i) in terms of the polynomial det(μA?λB) and the elementary divisors, minimal indices, and inertial signatures of the pencil μA?λB. This result contains, as a special case, the classical interlacing relationship governing the eigenvalues of a principal sub- matrix of a Hermitian matrix. The second main result is the determination of the number of different values of i to which the characterization just described can be simultaneously applied.     

The generalized Eckart-Young principal axis theorem

A rectangular matrix [a_pq ] is said to be diagonal if a_pq = 0 when p ≠ q. We present a simple proof of the following theorem of Wiegmann, but in principle given earlier by Eckart and Young: THEOREM If {A_i) is a set of complex r – s matrices such thatA A andA A are Hermitian for all i andj, then there exist unitary matrices P and Q such that for each i the matrixpA Q is real and diagonal Special cases of the above are well known and extremely useful. For example, the case n = 1 yields the classical singular value decomposition.     

On maximization of quadratic form over intersection of ellipsoids with common center

We demonstrate that if A ₁,...,A _m are symmetric positive semidefinite n×n matrices with positive definite sum and A is an arbitrary symmetric n×n matrix, then the relative accuracy, in terms of the optimal value, of the semidefinite relaxation of the optimization program is not worse than . It is shown that this bound is sharp in order, as far as the dependence on m is concerned, and that a~feasible solution x to (P) with can be found efficiently. This somehow improves one of the results of Nesterov [4] where bound similar to (*) is established for the case when all A_i are of rank 1. Received August 13, 1998 / Revised version received May 25, 1999? Published online September 15, 1999     

Saving flops in LU based shift-and-invert strategy

The shift-and-invert method is very efficient in eigenvalue computations, in particular when interior eigenvalues are sought. This method involves solving linear systems of the form (A−σI)z=b. The shift σ is variable, hence when a direct method is used to solve the linear system, the LU factorization of (A−σI) needs to be computed for every shift change. We present two strategies that reduce the number of floating point operations performed in the LU factorization when the shift changes. Both methods perform first a preprocessing step that aims at eliminating parts of the matrix that are not affected by the diagonal change. This leads to about 43% and 50% flops savings respectively for the dense matrices.     

On co-positive,semi-monotoneQ-matrices

In this paper we consider not necessarily symmetric co-positive as well as semi-monotoneQ-matrices and give a set of sufficient conditions for such matrices to beR ₀-matrices. We give several examples to show the sharpness of our results. Construction of these examples is based on the following elementary proposition: IfA is a square matrix of ordern whose first two rows are identical and bothA ₁₁ andA ₂₂ areQ-matrices whereA _ii stands for the principal submatrix ofA obtained by deleting rowi and columni fromA, thenA is aQ-matrix.Dedicated to our colleague and friend B. Ramachandran on his sixtieth birthday.Corresponding author.