Schur-type stability properties and complex diagonal scaling

We introduce new classes of n-by-n matrices with complex entries which can be scaled by a diagonal matrix with complex entries to be normal or Hermitian and study the Schur-type stability properties of these matrices.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Properties of normalr-potent matrices

The main goal of this paper is to present several new results concerning r-potent matrices which are also assumed to be normal. Included will be a theorem on the Moore-Penrose generalized inverse of a normal r-potent matrix, an equivalent characterization of a normal r-potent matrix, and some other basic properties. Finally, a generalization of the algebraic formulation of Cochran's theorem will be developed for complex normalr-potent matrices.     

Tournament matrices and their generalizations,I.

If M is any complex matrix with rank (M + M ^* + I) = 1, we show that any eigenvalue of M that is not geometrically simple has 1/2 for its real part. This generalizes a recent finding of de Caen and Hoffman: the rank of any n × n tournament matrix is at least n ? 1. We extend several spectral properties of tournament matrices to this and related types of matrices. For example, we characterize the singular real matrices M with 0 diagonal for which rank (M + M^T + I) = 1 and we characterize the vectors that can be in the kernels of such matrices. We show that singular, irreducible n × n tournament matrices exist if and only n? {2,3,4,5} and exhibit many infinite families of such matrices. Connections with signed digraphs are explored and several open problems are presented.     

Quadratically normal and congruence-normal matrices

A matrix A ∈ C ^n×n is unitarily quasidiagonalizable if A can be brought by a unitary similarity transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. In particular, the square roots of normal matrices, i.e., the so-called quadratically normal matrices are unitarily quasidiagonalizable. A matrix A ∈ C ^n×n is congruence-normal if B = A[`(A)] B = A\overline A is a conventional normal matrix. We show that every congruence-normal matrix A can be brought by a unitary congruence transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. Our proof emphasizes andexploitsalikenessbetween theequations X <sup>2</sup> = B and X[`(X)] = B X\overline X = B for a normal matrix B. Bibliography: 13 titles.     

Construction of Matrices with Prescribed Singular Values and Eigenvalues

Two issues concerning the construction of square matrices with prescribe singular values an eigenvalues are addressed. First, a necessary and sufficient condition for the existence of an n × n complex matrix with n given nonnegative numbers as singular values an m ( n) given complex numbers to be m of the eigenvalues is determined. This extends the classical result of Weyl and Horn treating the case when m = n. Second, an algorithm is given to generate a triangular matrix with prescribe singular values an eigenvalues. Unlike earlier algorithms, the eigenvalues can be arranged in any prescribe order on the diagonal. A slight modification of this algorithm allows one to construct a real matrix with specified real an complex conjugate eigenvalues an specified singular values. The construction is done by multiplication by diagonal unitary matrices, permutation matrices and rotation matrices. It is numerically stable and may be useful in developing test software for numerical linear algebra packages.     

The structured distance to normality of banded Toeplitz matrices

Spectral properties of normal (2k+1)-banded Toeplitz matrices of order n, with k≤⌊ n/2⌋, are described. Formulas for the distance of (2k+1)-banded Toeplitz matrices to the algebraic variety of similarly structured normal matrices are presented.     

Degrees of nonlinearity in forbidden 0–1 matrix problems

A 0–1 matrix A is said to avoid a forbidden 0–1 matrix (or pattern) P if no submatrix of A matches P, where a 0 in P matches either 0 or 1 in A. The theory of forbidden matrices subsumes many extremal problems in combinatorics and graph theory such as bounding the length of Davenport–Schinzel sequences and their generalizations, Stanley and Wilf’s permutation avoidance problem, and Turán-type subgraph avoidance problems. In addition, forbidden matrix theory has proved to be a powerful tool in discrete geometry and the analysis of both geometric and non-geometric algorithms.Clearly a 0–1 matrix can be interpreted as the incidence matrix of a bipartite graph in which vertices on each side of the partition are ordered. Füredi and Hajnal conjectured that if P corresponds to an acyclic graph then the maximum weight (number of 1s) in an n×n matrix avoiding P is O(nlogn). In the first part of the article we refute of this conjecture. We exhibit n×n matrices with weight Θ(nlognloglogn) that avoid a relatively small acyclic matrix. The matrices are constructed via two complementary composition operations for 0–1 matrices. In the second part of the article we simplify one aspect of Keszegh and Geneson’s proof that there are infinitely many minimal nonlinear forbidden 0–1 matrices. In the last part of the article we investigate the relationship between 0–1 matrices and generalized Davenport–Schinzel sequences. We prove that all forbidden subsequences formed by concatenating two permutations have a linear extremal function.     

On the Properties of Accretive-Dissipative Matrices

Let A be a complex n × n matrix, and let A = B + iC, B = B*, C = C* be its Toeplitz decomposition. Then A is said to be (strictly) accretive if B > 0 and (strictly) dissipative if C > 0. We study the properties of matrices that satisfy both these conditions, in other words, of accretive-dissipative matrices. In many respects, these matrices behave as numbers in the first quadrant of the complex plane. Some other properties are natural extensions of the corresponding properties of Hermitian positive-definite matrices.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 832–843.Original Russian Text Copyright ©2005 by A. George, Kh. D. Ikramov.     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

On a sub‐Stiefel Procrustes problem arising in computer vision

A sub‐Stiefel matrix is a matrix that results from deleting simultaneously the last row and the last column of an orthogonal matrix. In this paper, we consider a Procrustes problem on the set of sub‐Stiefel matrices of order n. For n = 2, this problem has arisen in computer vision to solve the surface unfolding problem considered by R. Fereirra, J. Xavier and J. Costeira. An iterative algorithm for computing the solution of the sub‐Stiefel Procrustes problem for an arbitrary n is proposed, and some numerical experiments are carried out to illustrate its performance. For these purposes, we investigate the properties of sub‐Stiefel matrices. In particular, we derive two necessary and sufficient conditions for a matrix to be sub‐Stiefel. We also relate the sub‐Stiefel Procrustes problem with the Stiefel Procrustes problem and compare it with the orthogonal Procrustes problem. Copyright © 2015 John Wiley & Sons, Ltd.     

The difference between doubly nonnegative and completely positive matrices

The convex cone of n×n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n×n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5×5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5×5 CP matrices.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

On the Multiplicative Monoid of n×n Matrices Over Artinian Chain Rings

Let R be an Artinian chain ring with a principal maximal ideal. We investigate properties of matrices over R and give matrix representations of R-submodules of R ⁿ first, then consider Green's relations, Green's relation equivalent classes, Schützenberger groups of 𝒟-classes, principal factors, and group ?-classes of the multiplicative monoid M _n (R) of n × n matrices over R. Furthermore, we show that M _n (R) is an eventually regular semigroup and derive basic numerical information of M _n (R) when R is finite.     

The structure of weighing matrices having large weights

We examine the structure of weighing matricesW(n, w), wherew=n–2,n–3,n–4, obtaining analogues of some useful results known for the casen–1. In this setting we find some natural applications for the theory ofsigned groups and orthogonal matrices with entries from signed groups, as developed in [3]. We construct some new series of Hadamard matrices from weighing matrices, including the following:W(n, n–2) implies an Hadamard matrix of order2n ifn0 mod 4 and order 4n otherwise;W(n, n–3) implies an Hadamard matrix of order 8n; in certain cases,W(n, n–4) implies an Hadamard matrix of order 16n. We explicitly derive 117 new Hadamard matrices of order 2 ^t p, p<4000, the smallest of which is of order 2³·419.Supported by an NSERC grant     

Smith meets Smith: Smith normal form of Smith matrix

In 1861, Henry John Stephen Smith [H.J.S. Smith, On systems of linear indeterminate equations and congruences, Philos. Trans. Royal Soc. London. 151 (1861), pp. 293–326] published famous results concerning solving systems of linear equations. The research on Smith normal form and its applications started and continues. In 1876, Smith [H.J.S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875/76), pp. 208–212] calculated the determinant of the n?×?n matrix ((i,?j)), having the greatest common divisor (GCD) of i and j as its ij entry. Since that, many results concerning the determinants and related topics of GCD matrices, LCM matrices, meet matrices and join matrices have been published in the literature. In this article these two important research branches developed by Smith, in 1861 and in 1876, meet for the first time. The main purpose of this article is to determine the Smith normal form of the Smith matrix ((i,?j)). We do this: we determine the Smith normal form of GCD matrices defined on factor closed sets.     

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.     

Some generators for the algebra of n×n matrices

In this note, we show how the algebra of n×n matrices over a field can be generated by a pair of matrices A B, where A is an arbitrary nonscalar matrix and B can be chosen so that there is the maximum degree of linear independence between the higher commutators of B with A.     

Supertropical matrix algebra II: Solving tropical equations

We continue the study of matrices over a supertropical algebra, proving the existence of a tangible adjoint of A, which provides the unique right (resp. left) quasi-inverse maximal with respect to the right (resp. left) quasi-identity matrix corresponding to A; this provides a unique maximal (tangible) solution to supertropical vector equations, via a version of Cramer’s rule. We also describe various properties of this tangible adjoint, and use it to compute supertropical eigenvectors, thereby producing an example in which an n × n matrix has n distinct supertropical eigenvalues but their supertropical eigenvectors are tropically dependent.     

Characterization of supercommuting matrices

For a given n–by–n matrix A, we consider the set of matrices which commute with A and all of whose principal submatrices commute with the corresponding principal submatrices of A. The properties of this set are examined, with particular attention to its dimension.