Computing the norm ∥A∥∞,1 is NP-hard ∗

It is proved that computing the subordinate matrix norm ∥A∥∞1 is NP-hard, Even more, existence of a polynomial-time algorithm for computing this norm with relative accuracy less than 1/(4n² ), where n is matrix size, implies P = NP.     

A result on integral symmetric matrices

Let A be an integral matrix such that det A = 1 mod mA ≡ A^T mod m, where m is odd. It is shown that a symmetric integral matrix B of determinant 1 exists such that B ≡ A mod m. The result is false if m is even.     

Subpermanents of doubly stochastic matrices

It is shown that if all subpermaneats of order k of an n × n doubly stochastic matrix are equal for some k ≤ n - 2, then all the entries of the matrix must be equal to 1/n.     

Permanents of doubly stochastic matrices with fixed zero pattern

The doubly stochastic matrices with a given zero pattern which are closest in Euclidean norm to J_nn, the matrix with each entry equal to 1/n, are identified. If the permanent is restricted to matrices having a given zero pattern confined to one row or to one column, the permanent achieves a local minimum at those matrices with that zero pattern which are closest to J_nn. This need no longer be true if the zeros lie in more than one row or column.     

On the S-matrix conjecture

Motivated with a problem in spectroscopy, Sloane and Harwit conjectured in 1976 what is the minimal Frobenius norm of the inverse of a matrix having all entries from the interval [0,1]$[0,1]$. In 1987, Cheng proved their conjecture in the case of odd dimensions, while for even dimensions he obtained a slightly weaker lower bound for the norm. His proof is based on the Kiefer–Wolfowitz equivalence theorem from the approximate theory of optimal design. In this note we give a short and simple proof of his result.     

The minimal polynomial of a matrix

Let Rbe a finite dimensional central simple algebra over a field FA be any n× n matrix over R. By using the method of matrix representation, this paper obtains the structure formula of the minimal polynomial q_A(λ) of A over F. By using q_A(λ), this paper discusses the structure of right (left) eigenvalues set of A, and obtains the necessary and sufficient condition that a matrix over a finite dimensional central division algebra is similar to a diagonal matrix.     

Some inequalities for commutators and an application to spectral variation. II

Inequalities that compare unitarily invariant norms of A - B and those of AΓ - ΓB and Γ^-1A - B Γ^-1 are obtained, where both A and B are either Hermitian or unitary or normal operators and Γ is a positive definite operator in a complex separable Hilbert space. These inequalities are then applied to derive bounds for spectral variation of diagonalisable matrices. Our new bounds improve substantially previously published bounds.     

Rotfel’d type inequalities for norms

In this note, we consider some norm inequalities related to the Rotfel’d Trace Inequality

     

Singularity, Wielandt’s lemma and singular values

In this study, some upper and lower bounds for singular values of a general complex matrix are investigated, according to singularity and Wielandt’s lemma of matrices. Especially, some relationships between the singular values of the matrix A and its block norm matrix are established. Based on these relationships, one may obtain the effective estimates for the singular values of large matrices by using the lower dimension norm matrices. In addition, a small error in Piazza (2002) [G. Piazza, T. Politi, An upper bound for the condition number of a matrix in spectral norm, J. Comput. Appl. Math. 143 (1) (2002) 141-144] is also corrected. Some numerical experiments on saddle point problems show that these results are simple and sharp under suitable conditions.     

Notes on D-optimal designs

The purpose of this paper is to exhibit new infinite families of D-optimal (0, 1)-matrices. We show that Hadamard designs lead to D-optimal matrices of size (j, mj) and (j − 1, mj), for certain integers j ≡ 3 (mod 4) and all positive integers m. For j a power of a prime and j ≡ 1 (mod 4), supplementary difference sets lead to D-optimal matrices of size (j, 2mj) and (j − 1, 2mj), for all positive integers m. We also show that for a given j and d sufficiently large, about half of the entries in each column of a D-optimal matrix are ones. This leads to a new relationship between D-optimality for (0, 1)-matrices and for (±1)-matrices. Known results about D-optimal (±1)-matrices are then used to obtain new D-optimal (0, 1)-matrices.     

Variance bounds, with an application to norm bounds for commutators

Murthy and Sethi [M.N. Murthy, V.K. Sethi, Sankhya Ser. B 27 (1965) 201-210] gave a sharp upper bound on the variance of a real random variable in terms of the range of values of that variable. We generalise this bound to the complex case and, more importantly, to the matrix case. In doing so, we make contact with several geometrical and matrix analytical concepts, such as the numerical range, and introduce the new concept of radius of a matrix.We also give a new and simplified proof for a sharp upper bound on the Frobenius norm of commutators recently proven by Böttcher and Wenzel [A. Böttcher, D. Wenzel, The Frobenius norm and the commutator, Linear Algebra Appl. 429 (2008) 1864-1885] and point out that at the heart of this proof lies exactly the matrix version of the variance we have introduced. As an immediate application of our variance bounds we obtain stronger versions of Böttcher and Wenzel’s upper bound.     

Large spaces of symmetric matrices of bounded rank are decomposable

Let k and n be positive integers such that k≤n. Let S_n(F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n(F) is said to be a k-subspace if rank A≤k for every AεL.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n(F) is decomposable if there exists in Fⁿ a subspace W of dimension n-r such that x^tAx=0 for every xεWAεL.

We show here, under some mild assumptions on kn and F, that every k∥-subspace of S_n(F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n.     

On a theorem of Čebotarev

A new proof is given of the theorem that no submatrix of the p×p matrix S=(ζ^(i-1)(j-1)) is singular, where ζis a primitive pth root of unity and p is a prime. Some related results are also discussed.     

Equivalence constants for certain matrix norms II

We give an almost complete solution of a problem posed by Klaus and Li [A.-L. Klaus, C.-K. Li, Isometries for the vector (p, q) norm and the induced (p, q) norm, Linear and Multilinear Algebra 38 (1995) 315–332]. Klaus and Li’s problem, which arose during their investigations of isometries, was to relate the Frobenius (or Hilbert–Schmidt) norm of a matrix to various operator norms of that matrix. Our methods are based on earlier work of Feng [B.Q. Feng, Equivalence constants for certain matrix norms, Linear Algebra Appl. 374 (2003) 247–253] and Tonge [A. Tonge, Equivalence constants for matrix norms: a problem of Goldberg, Linear Algebra Appl. 306 (2000) 1–13], but introduce as a new ingredient some techniques developed by Hardy and Littlewood [G.H. Hardy, J.E. Littlewood, Bilinear forms bounded in space [p, q], Quart. J. Math. (Oxford) 5 (1934) 241–254].     

Some results on symplectic matrices

The principal results are that if A is an integral matrix such that AA^T is symplectic then A = CQ, where Q is a permutation matrix and C is symplectic; and that if A is a hermitian positive definite matrix which is symplectic, and B is the unique hermitian positive definite pth.root of A, where p is a positive integer, then B is also symplectic.     

Computing the optimal commuting matrix pairs

A matrix can be modified by an additive perturbation so that it commutes with any given matrix. In this paper, we discuss several algorithms for computing the smallest perturbation in the Frobenius norm for a given matrix pair. The algorithms have applications in 2-D direction-of-arrival finding in array signal processing. The work of first author was supported in part by NSF grant CCR-9308399. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Some involutory similarities

Matrices A,B over an arbitrary field F, when given to be similar to each other, are shown to be involutorily similar (over F) to each other (i.e.B = CAC^-1for some C = C^-1over F) in the following cases: (1)B= aI - Afor some a ε F and (2) B = A^-1. Result (2) for the cases where char F ≠ 2 is essentially a 1966 result of Wonenburger.     

Extremal patterns of distinct entries in vectors in the range of a matrix

For an m × n matrix A over a field F we consider the following quantities: μ(A), the maximum multiplicity of a field element as a component of a nonzero vector in the range of A, and δ(A), the minimum number of distinct entries in a nonzero vector in the range of A. In terms of ramk(A), we describe the set of possible values of μand δ and discuss the possible relations between them. We also develop a general affine geometric structure in which the sets of values of μ and δ may be characterized linear algebraically.     

On the maximum density of 0–1 matrices with no forbidden rectangles

This note provides bounds for the maximal number of ones allowed in an N × N 0–1 matrix, N=2ⁿ, in which there are no ‘forbidden rectangles’ of a special type.     

Hyman’s method revisited

The QR algorithm is considered one of the most reliable methods for computing matrix eigenpairs. However, it is unable to detect multiple eigenvalues and Jordan blocks. Matlab’s eigensolver returns heavily perturbed eigenvalues and eigenvectors in such cases and there is no hint for possible principal vectors. This paper calls attention to Hyman’s method as it is applicable for computing principal vectors and higher derivatives of the characteristic polynomial that may help to estimate multiplicity, an important information for more reliable computation. We suggest a test matrix collection for Jordan blocks. The first numerical tests with these matrices reveal that the computational problems are deeper than expected at the beginning of this work.