Upper bounds for nearly optimal diagonal scaling of matrices

Optimal diagonal scaling of an n×n matrix A consists in finding a diagonal matrix D that minimizes a condition number of AD. Often a nearly optimal scaling of A is achieved by taking a diagonal matrix D₁ such that all diagonal elements of D₁A^TAD₁ are equal to one. It is shown in this paper that the condition number of AD₁ can be at least (n/2)^1/2 times the minimal one. Some questions for a further research are posed.     

On Lyapunov scaling factors of real symmetric matrices

A necessary and sufficient condition for the identity matrix to be the unique Lyapunov scaling factor of a given real symmetric matrix A is given. This uniqueness is shown to be equivalent to the uniqueness of the identity matrix as a scaling D for which the kernels of A and AD are identical.     

Extending the notions of companion and infinite companion to matrix polynomials

The notion of infinite companion matrix is extended to the case of matrix polynomials (including polynomials with singular leading coefficient). For row reduced polynomials a finite companion is introduced as the compression of the shift matrix. The methods are based on ideas of dilation theory. Connections with systems theory are indicated. Applications to the problem of linearization of matrix polynomials, solution of systems of difference and differential equations and new factorization formulae for infinite block Hankel matrices having finite rank are shown. As a consequence, any system of linear difference or differential equations with constant coefficients can be transformed into a first order system of dimension n = deg det D.     

Diameter vulnerability of GC graphs

Concern over fault tolerance in the design of interconnection networks has stimulated interest in finding large graphs with maximum degree Δ and diameter D such that the subgraphs obtained by deleting any set of s vertices have diameter at most D′, this value being close to D or even equal to it. This is the so-called (Δ,D,D′,s)-problem. The purpose of this work has been to study this problem for s=1 on some families of generalized compound graphs. These graphs were designed by Gómez (Ars Combin. 29-B (1990) 33) as a contribution to the (Δ,D)-problem, that is, to the construction of graphs having maximum degree Δ, diameter D and an order large enough. When approaching the mentioned problem in these graphs, we realized that each of them could be redefined as a compound graph, the main graph being the underlying graph of a certain iterated line digraph. In fact, this new characterization has been the key point to prove in a suitable way that the graphs belonging to these families are solutions to the (Δ,D,D+1,1)-problem.     

Geometry of 2×2 Hermitian matrices II

Let Z be a field of characteristic ≠2, D be a quaternion division algebra over Z and have a nonstandard involution of the first kind. The fundamental theorem of geometry of 2× 2 Hermitian matrices over D are proved. Thus, if D is a quaternion division algebra over Z with an involution of the first kind, then the fundamental theorem of geometry of 2× 2 Hermitian matrices over D are obtained.     

Positive diagonal solutions to the Lyapunov equations

We study various stability type conditions on a matrix A related to the consistency of the Lyapunov equation AD+DA^t positive definite, where D is a positive diagonal matrix. Such problems arise in mathematical economics, in the study of time-invariant continuous-time systems and in the study of predator-prey systems. Using a theorem of the alternative, a characterization is given for all A satisfying the above equation. In addition, some necessary conditions for consistency and some related ideas are discussed. Finally, a method for constructing a solution D to the equation is given for matrices A satisfying certain conditions.     

Products of complic cosquares and pseudo-involutory matrices

LetF be a field with (nontrivial) involution (i.e.F-conjugation). A nonsingular matrix Aover Fis called a complic F-cosquare provided A=S^*-1for some matrix Sover Fand is called p.i. (pseudo-involutory) provided A=A^-1 It is shown that Ais a complic F-cosquare iff Ais the product of two p.i. matrices over Fand that det (AA)=1 iff Ais the product of two complic F-cosquares (hence iff A is the product of four p.i. matrices over F). It is conjectured that, except for one obvious case (2 x 2 matrices over the field of order 2), every unimodular matrix A over an arbitrary field Fis a product S¹ST:1T with S1 and Tover FThis conjecture is proved for matricesAof order ≤3.     

Uniqueness of the “nonsingular core” for Hermitian and other matrix pencils

Every pencil of hermitian matrices is conjunctive with a pencil of the form L ⊕ M, where L (the "minimal-indices" part) has no elementary divisors and M (the "nonsingular core") is a nonsingular pencil. Here it is shown that the conjunctivity type ofM is determined by that of L ⊕ M. The same method of proof applies to many other types of pencils, e.g. to congruence of pencils based on (1) a pair of symmetric matrices, (2) a pair of alternating matrices, or (3) a symmetric and an alternating matrix.     

Persymmetric determinants 5. Families of overlapping coaxial equivalent determinants

In an earlier paper the author constructed two infinite matrices and showed that they contain families of distinct submatrices whose determinants represent identical polynomials.

The object of this paper is to extend the earlier results in two directions. The first set of identities is closely related to the original set and may be regarded as a supplement to the original paper. The second set relates determinants whose elements are based partly on Stirling numbers of the Second Kind to polynomials whose terms are based on Stirling numbers of the First Kind.     

Degrees in a digraph whose nodes are graphs

By an f-graph we mean an unlabeled graph having no vertex of degree greater than f. Let D(n, f) denote the digraph whose node set is the set of f-graphs of order n and such that there is an arc from the node corresponding to graph H to the node corresponding to the graph K if and only if K is obtainable from H by the addition of a single edge. In earlier work, algorithms were developed which produce exact results about the structure of D(n, f), nevertheless many open problems remain. For example, the computation of the order and size of D(n, f) for a number of values of n and f have been obtained. Formulas for the order and size for f = 2 have also been derived. However, no closed form formulas have been determined for the order and size of D(n, f) for any value of f. Here we focus on questions concerning the degrees of the nodes in D(n,n − 1) and comment on related questions for D(n,f) for 2 f < n − 1.     

The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

Bounds on the error of fejer and clenshaw-curtis type quadrature for analytic functions

We consider the problem of integrating a function f : [-1,1] → R which has an analytic extension to an open disk D^r of radius r and center the origin, such that for any . The goal of this paper is to study the minimal error among all algorithms which evaluate the integrand at the zeros of the n-degree Chebyshev polynomials of first or second kind (Fejer type quadrature formulas) or at the zeros of (n-2)-degree Chebyshev polynomials jointed with the endpoints -1,1 (Clenshaw-Curtis type quadrature formulas), and to compare this error to the minimal error among all algorithms which evaluate the integrands at n points. In the case r > 1, it is easy to prove that Fejer and Clenshaw-Curtis type quadrature are almost optimal. In the case r = 1, we show that Fejer type formulas are not optimal since the error of any algorithm of this type is at least about n^-2. These results hold for both the worst-case and the asymptotic settings.     

Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields

We discuss a conjecture concerning the enumeration of nonsingular matrices over a finite field that are block companion and whose order is the maximum possible in the corresponding general linear group. A special case is proved using some recent results on the probability that a pair of polynomials with coefficients in a finite field is coprime. Connection with an older problem of Niederreiter about the number of splitting subspaces of a given dimension are outlined and an asymptotic version of the conjectural formula is established. Some applications to the enumeration of nonsingular Toeplitz matrices of a given size over a finite field are also discussed.     

A theorem of the alternatives for the equation Ax + B|x| = b

The following theorem is proved: given square matrices A, D of the same size, D nonnegative, then either the equation Ax + B|x| = b has a unique solution for each B with |B| ≤ D and for each b, or the equation Ax + B₀|x| = 0 has a nontrivial solution for some matrix B₀ of a very special form, |B₀| ≤ D; the two alternatives exclude each other. Some consequences of this result are drawn. In particular, we define a λ to be an absolute eigenvalue of A if |Ax| = λ|x| for some x ≠ 0, and we prove that each square real matrix has an absolute eigenvalue.     

Ranks of Solutions of the Matrix Equation AXB = C

The purpose of this article is to solve two problems related to solutions of a consistent complex matrix equation AXB = C : (I) the maximal and minimal ranks of solution to AXB = C , and (II) the maximal and minimal ranks of two real matrices X₀ and X₁ in solution X = X₀ + iX₁ to AXB = C . As applications, the maximal and minimal ranks of two real matrices C and D in generalized inverse (A + iB)^- = C + iD of a complex matrix A + iB are also examined.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

Between d-stability and sign-stability: the 3 × 3 case

[2] introduced a decreasing sequence of sets of real n × n matrices, which begins with the D-stable matrices and stops at the sign-stable matrices. It is not clear how many of the n sets in the sequence are distinct. This article documents the disappointment that in the first case where the sequence could contain a set which is neither the D-stable matrices nor the sign-stable matrices(viz., the case n = 3) it doesn't.     

Competitive on-line coverage of grid environments by a mobile robot

We describe in this paper two on-line algorithms for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithms, called Spanning Tree Covering (STC) algorithms, incrementally subdivide the planar area into a grid of D-size cells, while following a spanning tree of a grid graph whose nodes are 2D-size cells. The two STC algorithms cover general planar grids. The first, Spiral-STC, employs uniform weights on the grid-graph edges and generates spiral-like covering patterns. The second, Scan-STC, assigns lower weights to edges aligned with a particular direction and generates scan-like covering patterns along this direction. Both algorithms cover any planar grid using a path whose length is at most (n+m)D, where n is the total number of D-size cells and mn is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also demonstrate that any on-line coverage algorithm generates a covering path whose length is at least (2−)l_opt in worst case, where l_opt is the length of the optimal off-line covering path. Since (n+m)D2l_opt, the bound is tight and the STC algorithms are worst-case optimal. Moreover, in practical environments mn, and the STC algorithms generate close-to-optimal covering paths in such environments.     

Cell rotation graphs of strongly connected orientations of plane graphs with an application

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T⁻, thus (T,T⁻) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T⁻, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.     

A note on representations for the inverses of tridiagonal matrices

In this note, we propose an explicit representation with the nested sums for the entries of the inverses of general tridiagonal nonsingular matrices. Its equivalence with other particular representations, based on the combinatorial expressions or the continued fractions, is considered. In addition, an analytical representation for the entries of the finite sections of the resolvent of Jacobi matrices, in terms of its related orthogonal polynomials, is observed.