Extensions of the Hadamard determinant theorem

Denote byH _n the set ofn byn, positive definite hermitian matrices. Hadamard proved thath(A)≧det(A) for allA∈H _n, whereh(A) is the product of the main diagonal elements ofA. Subsequently, M. Marcus showed that per(A)≧h(A) for allA∈H _n. This article contains a result for all generalized matrix functions from which it follows thath(A)≧(per(A^1/n )) ⁿ ,A∈H _n.     

A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix

The question of whether a real matrix is symmetrizable via multiplication by a diagonal matrix with positive diagonal entries is reduced to the corresponding question for M-matrices and related to Hadamard products. In the process, for a nonsingular M-matrix A, it is shown that tr(A^-1A^T) ? n, with equality if and only if A is symmetric, and that the minimum eigenvalue of A^-1 ° A is ? 1 with equality in the irreducible case if and only if A is positive diagonally symmetrizable.     

Uniform and minimal {0,1} – cp matrices

Let A be an n?×?n real matrix. A is called {0,1}-cp if it can be factorized as A?=?BB ^T with b_ij =0 or 1. The smallest possible number of columns of B in such a factorization is called the {0,1}-rank of A. A {0,1}-cp matrix A is called minimal if for every nonzero nonnegative n?×?n diagonal matrix D, A-D is not {0,1}-cp, and r-uniform if it can be factorized as A=BB ^T, where B is a (0,?1) matrix with r 1s in each column. In this article, we first present a necessary condition for a nonsingular matrix to be {0,1}-cp. Then we characterize r-uniform {0,1}-cp matrices. We also obtain some necessary conditions and sufficient conditions for a matrix to be minimal {0,1}-cp, and present some bounds for {0,1}-ranks.     

Generalizations of Arnold’s version of Euler’s theorem for matrices

A recent result, conjectured by Arnold and proved by Zarelua, states that for a prime number p, a positive integer k, and a square matrix A with integral entries one has ${\textrm tr}(A^{p^k}) \equiv {\textrm tr}(A^{p^{k-1}}) ({\textrm mod}{p^k})${\textrm tr}(A^{p^k}) \equiv {\textrm tr}(A^{p^{k-1}}) ({\textrm mod}{p^k}). We give a short proof of a more general result, which states that if the characteristic polynomials of two integral matrices A,  B are congruent modulo p ^k then the characteristic polynomials of A ^p and B ^p are congruent modulo p ^k+1, and then we show that Arnold’s conjecture follows from it easily. Using this result, we prove the following generalization of Euler’s theorem for any 2 × 2 integral matrix A: the characteristic polynomials of A ^Φ(n) and A ^Φ(n)-ϕ(n) are congruent modulo n. Here ϕ is the Euler function, ?_i=1^l p_i^a_i\prod_{i=1}^{l} p_i^{\alpha_i} is a prime factorization of n and $\Phi(n)=(\phi(n)+\prod_{i=1}^{l} p_i^{\alpha_i-1}(p_i+1))/2$\Phi(n)=(\phi(n)+\prod_{i=1}^{l} p_i^{\alpha_i-1}(p_i+1))/2.     

Improving eigenvalue bounds using extra bounds

Bounds for various functions of the eigenvalues of a Hermitian matrix A, based on the traces of A and A², are improved. A technique is presented whereby these bounds can be improved by combining them with other bounds. In particular, the diagonal of A, in conjunction with majorization, is used to improve the bounds. These bounds all require O(n²) multiplications.     

Perturbation bounds for the Cholesky andQR factorizations

LetA, A+E be Hermitian positive definite matrices. Suppose thatA=LL ^H andA+E=(L+G)(L+G)^H are the Cholesky factorizations ofA andA+E, respectively. In this paper lower bounds and upper bounds on |G|/|L| in terms of |E|/|A| are given. Moreover, perturbation bounds are given for the QR factorization of a complexm ×n matrixA of rankn.This research was supported by the National Science Foundation of China and the Department of Mathematics of Linköping University in Sweden.     

NON-EMPTY CROSS-2-INTERSECTING FAMILIES OF SUBSETS

Let Cdenote the set of all k-subests of an n-set.Assume Alohtain in Ca,and A lohtain in (A,B) is called a cross-2-intersecting family if |A B≥2 for and A∈A,B∈B.In this paper,the best upper bounds of the cardinalities for non-empty cross-2-intersecting familles of a-and b-subsets are obtained for some a and b,A new proof for a Frankl-Tokushige theorem[6] is also given.     

Commuting Involution

We are given a semiprime unital ring A with * such that x*x = xx* for all elements x of A. We will show that both elements x + x* and xx* are central elements. In the case in which A is a quaternion algebra over a field F in the sense given by Albert, we show that * is unique and coincides with the canonical involution. We also provide specific constructions of quaternion division algebras A with canonical involution over a field F of one of the following types: (i) F is a function field in two variables over a ground field of unspecified characteristic; (ii) F is a function field over the Galois field GF(2ⁿ); and (iii) F is a function field over the Galois field GF(pⁿ) where p is an odd prime number and n is a natural number.     

Resolvent Estimates for Operators Belonging to Exponential Classes

For a, α > 0 let E(a, α) be the set of all compact operators A on a separable Hilbert space such that s _n (A) = O(exp(-an^α)), where s _n (A) denotes the n-th singular number of A. We provide upper bounds for the norm of the resolvent (zI − A)⁻¹ of A in terms of a quantity describing the departure from normality of A and the distance of z to the spectrum of A. As a consequence we obtain upper bounds for the Hausdorff distance of the spectra of two operators in E(a, α).      

Some Simple Estimates for the Singular Values of Matrices

Abstract We first provide a simple estimate for ||A~(-1)||_∞ and ||A~(-1)||_1 of a strictly diagonally dominant matrixA. On the Basis of the result, we obtain an estimate for the smallest singular value of A. Secondly, by scalingwith a positive diagonal matrix D, we obtain some simple estimates for the smallest singular value of an H-matrix, which is not necessarily positive definite. Finally, we give some examples to show the effectiveness ofthe new bounds.     

Joint bounds for the Perron roots of nonnegative matrices with applications

Given a finite set {A_x}_{x ∈ X} of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices D⁻¹ A^(x) D, x ∈ X, where D is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices A^(x) and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable. Bibliography: 20 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 30–56.     

Bounds on the subdominant eigenvalue involving group inverse with applications to graphs

Let A be an n × n symmetric, irreducible, and nonnegative matrix whose eigenvalues are ₁₂ ... _n. In this paper we derive several lower and upper bounds, in particular on ₂ and _n , but also, indirectly, on . The bounds are in terms of the diagonal entries of the group generalized inverse, Q ^#, of the singular and irreducible M-matrix Q = ₁ I – A. Our starting point is a spectral resolution for Q ^#. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected graphs, where now Q becomes L, the Laplacian of the graph. In case the graph is a tree we find a graph-theoretic interpretation for the entries of L ^# and we also sharpen an upper bound on the algebraic connectivity of a tree, which is due to Fiedler and which involves only the diagonal entries of L, by exploiting the diagonal entries of L ^#.     

Exponentially Many Hadamard Designs

If there is a Hadamard design of order n, then there are at least 2^{8n−16−9log n} non-isomorphic Hadamard designs of order 2n. Mathematics Subject Classificaion 2000: 05B05     

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     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

Lower bounds for the minimum eigenvalue of Hadamard product of an M-matrix and its inverse

For the Hadamard product A ° A⁻¹ of an M-matrix A and its inverse A⁻¹, we give new lower bounds for the minimum eigenvalue of A ° A⁻¹. These bounds are strong enough to prove the conjecture of Fiedler and Markham [An inequality for the Hadamard product of an M-matrix and inverse M-matrix, Linear Algebra Appl. 101 (1988) 1-8].     

On the tournament matrices with smallest rank

A tournament matrix is a square zero-one matrix A satisfying the equation A+A^t = J ? I, where J is the all-ones matrix. In [1] it was proved that if A is an n × n tournament matrix, then the rank of A is at least (n - 1)/2, over any field; and in characteristic zero rank (A) equals n - 1 or n. Michael [3] has constructed examples having rank (n - 1)/2; they are double borderings of Hadamard tournaments of order n - 2, and so must satisfy n ≡ 1 (mod 4). In this note, we supplement this result by showing that an analogous construction is sometimes impossible when n ≡ 3 (mod 4).     

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.     

The excess of complex Hadamard matrices

A complex Hadamard matrix,C, of ordern has elements 1, –1,i, –i and satisfiesCC ^*=nI_nwhereC ^* denotes the conjugate transpose ofC. LetC=[c _ij] be a complex Hadamard matrix of order is called the sum ofC. (C)=|S(C)| is called the excess ofC. We study the excess of complex Hadamard matrices. As an application many real Hadamard matrices of large and maximal excess are obtained.Supported by an NSERC grant.Supported by Telecom grant 7027, an ATERB and ARC grant # A48830241.