Flows on graphs applied to diagonal similarity and diagonal equivalence for matrices

Three equivalence relations are considered on the set of n × n matrices with elements in F₀, an abelian group with absorbing zero adjoined. They are the relations of diagonal similarity, diagonal equivalence, and restricted diagonal equivalence. These relations are usually considered for matrices with elements in a field. But only multiplication is involved. Thus our formulation in terms of an abelian group with o is natural. Moreover, if F is chosen to be an additive group, diagonal similarity is characterized in terms of flows on the pattern graph of the matrices and diagonal equivalence in terms of flows on the bipartie graph of the matrices. For restricted diagonal equivalence a pseudo-diagonal of the graph must also be considered. When no pseudo-diagonal is present, the divisibility properties of the group F play a role. We show that the three relations are characterized by cyclic, polygonal, and pseudo-diagonal products for multiplicative F. Thus, our method of reducing propositions concerning the three equivalence relations to propositions concerning flows on graphs, provides a unified approach to problems previously considered independently, and yields some n, w or improved results. Our consideration of cycles rather than circuits eliminates certain restrictions (e.g., the complete reducibility of the matrices) which have previously been imposed. Our results extend theorems in Engel and Schneider [5], where however the group F is permitted to be non-commutative.     

Similarity transformations of decomposable matrix polynomials and related questions

A relationship is found between the similarity transformations of decomposable matrix polynomials with relatively prime elementary divisors and the equivalence transformations of the corresponding matrices with scalar entries. Matrices with scalar entries are classified with respect to equivalence transformations based on direct sums of lower triangular almost Toeplitz matrices. This solves the similarity problem for a special class of finite matrix sets over the field of complex numbers. Eventually, this problem reduces to the one of special diagonal equivalence between matrices. Invariants of this equivalence are found.     

Cyclic and diagonal products on a matrix

We unify the theory of cyclic and diagonal products of elements of matrices. We obtain some new results on diagonal similarity, diagonal equivalence, complete reducibility and total support.     

The elementary divisor theory over the Hurwitz order of integral quaternions

There exists a diagonal form with certain divisibility conditions for matrices over the Hurwitz order of integral quaternions under unimodular equivalence. The diagonal entries are uniquely determined up to similarity. Given two such diagonal forms, where the diagonal entries are similar by pairs, the matrices prove to be ummodularly equivalent, whenever the rank of the matrices is creater than one.     

Quotient Stable Uniform Groups

Abstract

In a subclass of rigid almost completely decomposable groups with global homocyclic regulator quotient a classification up to near-isomorphism, in terms of modified diagonal similarity, and a decomposition criterion is given. This subclass contains the local uniform groups, and generalizations of results of Dugas and Oxford are obtained, first to some global case and second to modified diagonal similarity instead of diagonal equivalence.     

On the Reduction of a Complex Matrix to Triangular or Diagonal by Consimilarity

1 Introduction When studying time reversal of quantum mechanics, physicists often encounter antilinear trans- formations in complex vector spaces. An antilinear transformation T is a mapping from one mcmaonaamdtt rrpciiolcxene xsSj u v.Ag ea cCattoneo nrd…     

Tridiagonal and upper triangular inverse M-matrices

In this paper we characterize the nonnegative nonsingular tridiagonal matrices belonging to the class of inverse M-matrices. We give a geometric equivalence for a nonnegative nonsingular upper triangular matrix to be in this class. This equivalence is extended to include some reducible matrices.     

Invariant factors of integral quaternion matrices

Existence of a diagonal form under unimodular equivalence is proved for matrices with entries from the Hurwitz ring of integral quaternions. The diagonal elements satisfy certain divisibility relations with an unexpected character, and these force a degree of uniqueness to the diagonal form. Connections between the so obtained invariant factors of a full matrix and those of a submatrix are then established.     

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix. The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior point methods on dense problems with no structure and also on a class of sparse problems. This work has been completed with the partial support of a summer grant from the College of Business Administration, California State University San Marcos, and the University Professional Development/Research and Creative Activity Grant     

Constrained l1 estimation via geometric programming

The l₁ and constrained l₁ estimation problems are viewed in the light of extended geometric programming. As a result of this point of view we are able to establish an equivalence between geometric and linear programming duality results for these classes of problems. In addition, the duality results provide some useful insights into the properties of the l₁ estimation problems. Finally we establish an equivalence between the l_∞ norm problem and a class of constrained l₁ estimation problems.     

Sweeping-similarity of matrices

This partly expository paper deals with a canonical-form problem for finite sets of matrices. The problem generalizes matrix equivalence, matrix similarity, and simultaneous equivalence of pairs of matrices [(A,B) → (PAQ, PBQ)], as well as some more complicated matrix problems that originated in work of Nazarova and Roiter.     

Simultaneous decomplexification of a pair of complex matrices by a similarity transformation

The following question is treated: Under what conditions can complex n-by-n matrices A and B be made real by the same similarity transformation? It is shown that if the algebra generated by A and B contains a matrix with a simple real spectrum, then the problem of the simultaneous decomplexification of a matrix pair can be reduced to the decomplexification of a single matrix by a diagonal similarity transformation. From this result, sufficient conditions are derived for the possibility of simultaneous decomplexification. An example illustrating these conditions is given.     

反中心对称矩阵的广义特征值反问题

Given matrix X and diagonal matrix A , the anti-centrosymmetric solutions (A, B) and its optimal approximation of inverse generalized eigenvalue problem AX = BXA have been considered. The general form of such solutions is given and the expression of the optimal approximation solution to a given matrix is derived. The algorithm and one numerical example for solving optimal approximation solution are included.     

Roth's theorems for sets of matrices

It is shown that Roth's theorems on the equivalence and similarity of block diagonal matrices hold for finite sets of matrices over a commutative ring.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Maximum principle for optimal control of distributed-parameter systems with singular mass matrix

A maximum principle for the open-loop optimal control of a vibrating system relative to a given convex index of performance is investigated. Though maximum principles have been studied by many people (see, e.g., Refs. 1–5), the principle derived in this paper is of particular use for control problems involving mechanical structures. The state variable satisfies general initial conditions as well as a self-adjoint system of partial differential equations together with a homogeneous system of boundary conditions. The mass matrix is diagonal, constant, and singular, and the viscous damping matrix is diagonal. The maximum principle relates the optimal control with the solution of the homogeneous adjoint equation in which terminal conditions are prescribed in terms of the terminal values of the optimal state variable. An application of this theory to a structural vibrating system is given in a companion paper (Ref. 6).     

Column Generation Algorithms for Nonlinear Optimization,I: Convergence Analysis

Column generation is an increasingly popular basic tool for the solution of large-scale mathematical programming problems. As problems being solved grow bigger, column generation may however become less efficient in its present form, where columns typically are not optimizing, and finding an optimal solution instead entails finding an optimal convex combination of a huge number of them. We present a class of column generation algorithms in which the columns defining the restricted master problem may be chosen to be optimizing in the limit, thereby reducing the total number of columns needed. This first article is devoted to the convergence properties of the algorithm class, and includes global (asymptotic) convergence results for differentiable minimization, finite convergence results with respect to the optimal face and the optimal solution, and extensions of these results to variational inequality problems. An illustration of its possibilities is made on a nonlinear network flow model, contrasting its convergence characteristics to that of the restricted simplicial decomposition (RSD) algorithm.     

Matrix representations of fourth-order boundary value problems with coupled or mixed boundary conditions

An equivalence between a class of regular self-adjoint fourth-order boundary value problems with coupled or mixed boundary conditions and a certain class of matrix problems is investigated. Such an equivalence was previously known only in the second-order case and fourth-order case with separated boundary conditions.     

Remarks on Lipschitz properties of matrix groups actions

It is proved that a large class of matrix group actions, including joint similarity and congruence-like actions, as well as actions of the type of matrix equivalence, have local Lipschitz property. Under additional hypotheses, global Lipschitz property is proved. These results are specialized and applied to obtain local Lipschitz property of canonical bases of matrices that are selfadjoint in an indefinite inner product. Real, complex, and quaternionic matrices are considered.