The rank of the difference of matrices with prescribed similarity classes

Let F be a field and let A,B be n × n matrices over I. We study the rank of A' - B' when A and B run over the set of matrices similar to A and B, respectively.     

The eigenvalues of the product of matrices with prescribed similarity classes *

Let A and B be n × n nonsingular matrices over a field F, and c ₁,…,c _n ∈ F. We give a necessary and sufficient condition for the existence of matrices A′ and B′ similar to A and B, respectively, such that A′ B′ has eigenvalues c ₁,…,c _n.     

Existence of matrices with prescribed entries

It is proved that, apart from for some exceptional cases, there always exists an n×n nonderogatory matrix over an arbitrary field with n prescribed entries and prescribed characteristic polynomial.     

Sums of integral matrices

A study is begun of the behavior of invariant factors when integral matrices are added.     

Sums and products with smooth numbers

We estimate the sizes of the sumset A+A and the productset A⋅A in the special case that A=S(x,y), the set of positive integers n?x free of prime factors exceeding y.     

Existence of matrices with prescribed eigenvalues and entries

It is proved improving a previous result of Oliveira that apart from two exceptions there always exists an n×n matrix with arbitarily prescribed 2n-3 entries and spectrum. Moreover, it is shown that the number 2n 3 of prescribed entries cannot be increased.     

Nonnegative matrices with prescribed spectrum and elementary divisors

In this paper we give new sufficient conditions for the existence and construction of nonnegative matrices with prescribed elementary divisors, which drastically improve and contain some of the previous known conditions. We also show how to perturb complex eigenvalues of a nonnegative matrix while keeping its nonnegativity. These results allow us, under certain conditions, to easily decide if a given list is realizable with prescribed elementary divisors.     

Doubly stochastic matrices with prescribed positive spectrum

We show that for every set Λ={λ₁,λ₂,…,λ_n} of real numbers such that $\text{λ}{}_1\text{=1?λ}{}_2\text{???λ}{}_{\mathrm{n}}\text{\&\#62;0}$, there exists a doubly stochastic matrix with spectrum Λ. We present an explicit construction of such a matrix.     

Constructing all self-adjoint matrices with prescribed spectrum and diagonal

The Schur–Horn Theorem states that there exists a self-adjoint matrix with a given spectrum and diagonal if and only if the spectrum majorizes the diagonal. Though the original proof of this result was nonconstructive, several constructive proofs have subsequently been found. Most of these constructive proofs rely on Givens rotations, and none have been shown to be able to produce every example of such a matrix. We introduce a new construction method that is able to do so. This method is based on recent advances in finite frame theory which show how to construct frames whose frame operator has a given prescribed spectrum and whose vectors have given prescribed lengths. This frame construction requires one to find a sequence of eigensteps, that is, a sequence of interlacing spectra that satisfy certain trace considerations. In this paper, we show how to explicitly construct every such sequence of eigensteps. Here, the key idea is to visualize eigenstep construction as iteratively building a staircase. This visualization leads to an algorithm, dubbed Top Kill, which produces a valid sequence of eigensteps whenever it is possible to do so. We then build on Top Kill to explicitly parametrize the set of all valid eigensteps. This yields an explicit method for constructing all self-adjoint matrices with a given spectrum and diagonal, and moreover all frames whose frame operator has a given spectrum and whose elements have given lengths.     

Simultaneous similarity of matrices

In this paper we solve completely and explicitly the long-standing problem of classifying pairs of n × n complex matrices (A, B) under the simultaneous similarity (TAT⁻¹, TBT⁻¹). Roughly speaking, the classification decomposes to a finite number of steps. In each step we consider an open algebraic set ⁰_n,2,r,π M_n × M_n (M_n = the set of n × n complex-valued matrices). Here r and π are two positive integers. Then we construct a finite number of rational functions ø₁,…,ø_s in the entries of A and B whose values are constant on all pairs similar in _n,2,r,π to (A, B). The values of the functions ø_i(A, B), I = 1,…, s, determine a finite number (at most κ(n, 2, r)) of similarity classes in _n,2,r,π. Let S_n be the subspace of complex symmetric matrices in M_n. For (A, B) ε S_n × S_n we consider the similarity class (TAT^t, TBT^t), where T ranges over all complex orthogonal matrices. Then the characteristic polynomial |λI − (A + xB)| determines a finite number of similarity classes for almost all pairs (A, B) ε S_n × S_n.     

The existence of matrices with prescribed characteristic and permanental polynomials

Let d(λ) and p(λ) be monic polynomials of degree n?2 with coefficients in F, an algebraically closed field or the field of all real numbers. Necessary and sufficient conditions for the existence of an n-square matrix A over F such that det(λI?A)=d(λ) and per(λI?A=p(λ) are given in terms of the coefficients of d(λ) and p(λ).     

On controllability of partially prescribed matrices

Let A₁and A₂be matrices of sizes m×m and m×n, respectively. Suppose that some of the entries under the main diagonal of A₁ are unknown and all the other entries of [A₁ A₂] are constant. We study the existence of a completely controllable completion of (A₁,A₂) and generalize a previous result on the same problem.     

Extending subpermutation matrices in regular classes of matrices

We determine precise conditions in order that every n × n matrix of 0's and 1's with exactly k 1's in each row and column has the property that each subpermutation matrix of rank d can be extended to a permutation matrix. An application is given to completing partial latin squares.     

Sums and products along sparse graphs

In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n ^1+ɛ distinct sums of pairs or that many distinct products, and conjectured a lower bound of n ^2−o(1). They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given graph G on n labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least n ^1+ɛ edges.