The Number of Negative Entries in a Sign Pattern Allowing Orthogonality

A ± sign pattern is a matrix whose entries are in the set {+,–}. An n×n ± sign pattern A allows orthogonality if there exists a real orthogonal matrix B in the qualitative class of A. In this paper, we prove that for n3 there is an n×n ± sign pattern A allowing orthogonality with exactly k negative entries if and only if n–1kn²–n+1.Research supported by Shanxi Natural Science Foundation 20011006, 20041010Final version received: October 22, 2003     

Conjugate-gradient method for computing the Moore-Penrose inverse and rank of a matrix

A conjugate-gradient method is developed for computing the Moore-Penrose generalized inverseA of a matrix and the associated projectors, by using the least-square characteristics of both the method and the inverseA . Two dual algorithms are introduced for computing the least-square and the minimum-norm generalized inverses, as well asA . It is shown that (i) these algorithms converge for any starting approximation; (ii) if they are started from the zero matrix, they converge toA ; and (iii) the trace of a sequence of approximations multiplied byA is a monotone increasing function converging to the rank ofA. A practical way of compensating the self-correcting feature in the computation ofA is devised by using the duality of the algorithms. Comparison with Ben-Israel's method is made through numerical examples. The conjugate-gradient method has an advantage over Ben-Israel's method.After having completed the present paper, the author received from Professor M. R. Hestenes his paper entitledPseudo Inverses and Conjugate Gradients. This paper treated the same subject and appeared in Communications of the ACM, Vol. 18, pp. 40–43, 1975.     

Locally most powerful rank tests for testing randomness and symmetry

Let X _i, 1 i N, be N independent random variables (i.r.v.) with distribution functions (d.f.) F _i(x,), 1 i N, respectively, where is a real parameter. Assume furthermore that F _i(·,0) = F(·) for 1 i N. Let R = (R ₁,R _N) and R ⁺,...,R _N ⁺ be the rank vectors of X = (X ₁,X _N) and |X|=(|X ₁|,...,|X _N|), respectively, and let V = (V ₁,V _N) be the sign vector of X. The locally most powerful rank tests (LMPRT) S = S(R) and the locally most powerful signed rank tests (LMPSRT) S = S(R ⁺, V) will be found for testing = 0 against > 0 or < 0 with F being arbitrary and with F symmetric, respectively.     

Homotopy stability of orthogonal spaces in commutative banach algebras

We study the concept of real stable rank for a complex commutative Banach algebra A (rsr A). It is shown that this invariant has a behaviour completely analogous to the classical Bass stable rank; in particular, we establish a precise relation between both invariants.Further, we use this machinery to show that the connected components of the orthogonal spaces of A, O _k ⁿ (A)={ A ^k×n:^t=id_k×k}, stabilize when k and n increase in a way that depends on rsr A Finally, we prove an analogous stabilization result for the homotopy classes of maps from the j-sphere into O _k ⁿ (A), where j is an arbitrary positive integer.Research supported by a grant of the CONICET, Argentina.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.     

Two Splittings of a Square Matrix

In this note it is shown that any square matrix AC ^n×n can be represented as the sum A= , where is complex symmetric and rank . The corresponding persymmetric result can be used in finding the terms of a small rank perturbed Toeplitz matrix via an O(n ²) computation. This allows one to perform fast matrix–vector products in case n is large.     

Powers of matrices over an extremal algebra with applications to periodic graphs

Consider the extremal algebra=({},min,+), using + and min instead of addition and multiplication. This extremal algebra has been successfully applied to a lot of scheduling problems. In this paper the behavior of the powers of a matrix over is studied. The main result is a representation of the complete sequence (A ^m ) _m which can be computed within polynomial time complexity. In the second part we apply this result to compute a minimum cost path in a 1-dimensional periodic graph.     

On the convergence of the symmetric SOR method for matrices with red-black ordering

Summary We prove that if the matrixA has the structure which results from the so-called red-black ordering and ifA is anH-matrix then the symmetric SOR method (called the SSOR method) is convergent for 0<<2. In the special case thatA is even anM-matrix we show that the symmetric single-step method cannot be accelerated by the SSOR method. Symmetry of the matrixA is not assumed.     

广义星符号模式的秩

一个符号模式是一个元素取自于集合{ ,-,0)的矩阵.如果符号模式A是组合对称的, 且它的图是一个广义星图,则称A是广义星符号模式.对于任意的广义星符号模式(可能有非零对角元),本文给出其最小秩的界.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

Resolution of the Symmetric Nonnegative Inverse Eigenvalue Problem for Matrices Subordinate to a Bipartite Graph

There is a symmetric nonnegative matrix A, subordinate to a given bipartite graph G on n vertices, with eigenvalues _{12 n} if and only if, ₁ + _n 0, ₂ + _n-10,..., _m + _{n - m + 1}0, _{m + 1}0,..., _{n - m} 0, in which m is the matching numberof G. Other observations are also made about the symmetric nonnegative inverse eigenvalue problem with respect to a graph     

The erdös-dushnik-miller theorem for topological graphs and orders

A topological graph is a graph G=(V, E) on a topological space V such that the edge set E is a closed subset of the product space V x V. If the graph contains no infinite independent set then, by a well-known theorem of Erdös, Dushnik and Miller, for any infinite set LV, there is a subset LL of the same oardinality |L| = |L| such that the restriction G L is a complete graph. We investigate the question of whether the same conclusion holds if we weaken the hypothesis and assume only that some dense subset AV does not contain an infinite independent set. If the cofinality cf (|L|)>|A|, then there is an L as before, but if cf (|L|)<-|A|, then some additional hypothesis seems to be required. We prove that, if the graph GA is a comparability graph and A is a dense subset, then for any set LV such that cf (|L|)>, there is a subset LL of size |L|=|L| such that GL is complete. The condition cf (|L|)> is needed.Research supported by NSERC grant #A5198.     

A note on universally optimal matrices and field independence of the minimum rank of a graph

For a simple graph G on n vertices, the minimum rank of G over a field F, written as mr^F(G), is defined to be the smallest possible rank among all n×n symmetric matrices over F whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. A symmetric integer matrix A such that every off-diagonal entry is 0, 1, or -1 is called a universally optimal matrix if, for all fields F, the rank of A over F is the minimum rank of the graph of A over F. Recently, Dealba et al. [L.M. Dealba, J. Grout, L. Hogben, R. Mikkelson, K. Rasmussen, Universally optimal matrices and field independence of the minimum rank of a graph, Electron. J. Linear Algebra 18 (2009) 403-419] initiated the study of universally optimal matrices and established field independence or dependence of minimum rank for some families of graphs. In the present paper, more results on universally optimal matrices and field independence or dependence of the minimum rank of a graph are presented, and some results of Dealba et al. [5] are improved.     

Solving Toeplitz Least Squares Problems by Means of Newton's Iteration

We extend the algorithm of [4], based on Newton's iteration and on the concept of -displacement rank, to the computation of the generalized inverse A ⁺ of an m×n Toeplitz matrix A. We introduce new strategies for the dynamical control of the truncation level at each step of the iteration. Numerical experiments and an application to a problem of image restoration are shown. An object-oriented implementation in C++ is described.     

Minimum steiner trees in normed planes

A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the unit disk is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio(D) forD, and show that, for anyD, 0.623<(D)<0.8686.Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.     

Maximally Symmetric Trees

We characterize the best model geometries for the class of virtually free groups, and we show that there is a countable infinity of distinct best model geometries in an appropriate sense – these are the maximally symmetric trees. The first theorem gives several equivalent conditions on a bounded valence, cocompact tree T without valence 1 vertices saying that T is maximally symmetric. The second theorem gives general constructions for maximally symmetric trees, showing for instance that every virtually free group has a maximally symmetric tree for a model geometry.     

An algorithm for determining if the inverse of a strictly diagonally dominant Stieltjes matrix is strictly ultrametric

Summary It was recently shown that the inverse of a strictly ultrametric matrix is a strictly diagonally dominant Stieltjes matrix. On the other hand, as it is well-known that the inverse of a strictly diagonally dominant Stieltjes matrix is a real symmetric matrix with nonnegative entries, it is natural to ask, conversely, if every strictly diagonally dominant Stieltjes matrix has a strictly ultrametric inverse. Examples show, however, that the converse is not true in general, i.e., there are strictly diagonally dominant Stieltjes matrices in ^n×n (for everyn3) whose inverses are not strictly ultrametric matrices. Then, the question naturally arises if one can determine which strictly diagonally dominant Stieltjes matrices, in ^n×n (n3), have inverses which are strictly ultrametric. Here, we develop an algorithm, based on graph theory, which determines if a given strictly diagonally dominant Stieltjes matrixA has a strictly ultrametric inverse, where the algorithm is applied toA and requires no computation of inverse. Moreover, if this given strictly diagonally dominant Stieltjes matrix has a strictly ultrametric inverse, our algorithm uniquely determines this inverse as a special sum of rank-one matrices.Research supported by the National Science FoundationResearch supported by the Deutsche Forschungsgemeinschaft     

Einstein Metrics with Nonpositive Sectional Curvature on Extensions of Lie Algebras of Heisenberg Type

The purpose of this article is to study some simply connected Lie groups with left invariant Einstein metric, negative Einstein constant and nonpositive sectional curvature. These Lie groups are classified if their associated metric Lie algebra s is of Iwasawa type and s = An₁n₂...n_r, where all n_iare Lie algebras of Heisenberg type with [[n_i,n_j] = {0} for ij. The most important ideas of the article are based on a construction method for Einstein spaces introduced by Wolter in 1991. By this method some new examples of Einstein spaces with nonpositive curvature are constructed. In another part of the article it is shown that Damek-Ricci spaces have negative sectional curvature if and only if they are symmetric spaces.     

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.