On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

Two inequalities for the Perron Root

If A,B are irreducible, nonnegative n×n matrices with a common right eigenvector and a common left eigenvector corresponding to their respective spectral radii r(A), r(B), then it is shown that for any tϵ[0, 1], r(tA+(1−t)B^t)⩾tr(A)+ (1−t)r(B), where B^t is the transpose of B. Another inequality is proved that involves r(A) and r(Σ_lD^lAE^l), where A is a nonnegative, irreducible matrix and D^l, E^l are positive definite diagonal matrices. These inequalities generalize previous results due to Levinger and due to Friedland and Karlin.     

On the numbers of positive entries of reducible nonnegative matrices

Let RM(n,d) be the class {A∣A is an n×n reducible nonnegative matrix and the greatest common divisor of the lengths of all cycles in D(A) is d}, where D(A) is the associated digraph of A. In this paper we determine the set of numbers of positive entries of A for A∈RM(n,d). We also characterize the reducible nonnegative matrices with the maximum and minimum numbers of positive entries.     

Inequalities and identities for generalized matrix functions

Let χ be a character on the symmetric group S_n, and let A = (a_ij) be an n-by-n matrix. The function d_χ(A) = Σ_σ?Snχ(σ)Πⁿ_{t = 1}a_tσ(t) is called a generalized matrix function. If χ is an irreducible character, then d_χ is called an immanent. For example, if χ is the alternating character, then d_χ is the determinant, and if χ ≡ 1, then d_χ is called the permanent (denoted per). Suppose that A is positive semidefinite Hermitian. We prove that the inequality $\text{(1/χ(}\text{id}\text{))d}{}_{\mathrm{\chi }}\text{(A) ?}\text{per}\text{A}$ holds for a variety of characters χ including the irreducible ones corresponding to the partitions (n ? 1,1) and (n ? 2,1,1) of n. The main technique used to prove these inequalities is to express the immanents as sums of products of principal subpermanents. These expressions for the immanents come from analogous expressions for Schur polynomials by means of a correspondence of D.E. Littlewood.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

A note on a conjecture on permanents

Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on K_n defined by ϕ (X) = Πⁿ_i=1Σⁿ_j=1x_ij + Πⁿ_j=1Σⁿ_i=1x_ij − per X for X = [x_ij] ϵ K_n. A matrix A ϵ K_n is called a ϕ -maximizing matrix on K_n if ϕ (A) ⩾ ϕ (X) for all X ϵ K_n. It is conjectured that J_n = [1/n]_{n × n} is the unique ϕ-maximizing matrix on K_n. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = J_n. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = J_n. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nⁿ and 1 + (n − 1)√2·n!/nⁿ. (iv) For any p.s.d. symmetric A ϵ K_n, ϕ (A) ⩽ 2 − n!/nⁿ with equality iff A = J_n. (v) ϕ attains a strict local maximum on K_n at J_n.     

A relationship between stochastic matrices and eigenvalues of products

Let {B₁,…,B_n} be a set of n rank one n×n row stochastic matrices. The next two statements are equivalent: (1) If A is an n×n nonnegative matrix, then 1 is an eigenvalue ofB_kA for each k=1,…,n if and only if A is row stochastic. (2) The n×n row stochastic matrix S whose kth row is a row of B_k for k=1,…,n is nonsingular. For any set {B₁, B₂,…, B_p} of fewer than n row stochastic matrices of order n×n and of any rank, there exists a nonnegative n×n matrix A which is not row stochastic such that 1 is eigenvalue of every B_kA, k=1,…,p.     

On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator

The paper is devoted to the implementations of the public key algorithms based on simple algebraic graphs A(n, K) and D(n, K) defined over the same finite commutative ring K. If K is a finite field both families are families of graphs with large cycle indicator. In fact, the family D(n, F _q ) is a family of graphs of large girth (f.g.l.g.) with c =?1, their connected components CD(n, F _q ) form the f.g.l.g. with the speed of growth 4/3. Family A(n, q), char F _q ?? 2 is a family of connected graphs with large cycle indicator with the largest possible speed of growth. The computer simulation demonstrates the advantage (better density which is the number of monomial expressions) of public rules derived from A(n, q) in comparison with symbolic algorithm based on graphs D(n, q).     

Hyperelliptic jacobians with real multiplication

Let K be a field of characteristic p≠2, and let f(x) be a sextic polynomial irreducible over K with no repeated roots, whose Galois group is isomorphic to A₅. If the jacobian J(C) of the hyperelliptic curve C:y²=f(x) admits real multiplication over the ground field from an order of a real quadratic field D, then either its endomorphism algebra is isomorphic to D, or p>0 and J(C) is a supersingular abelian variety. The supersingular outcome cannot occur when p splits in D.     

Spherical functions and immanants

Let λ be an irreducible character of S_n corresponding to the partition (r,s) of n. Let A be a positive semidefinite Hermitian n × n matrix. Let d_λ (A) and per(A) be the immanants corresponding to λ and to the trivial character of S_n , respectively. A proof of the inequality dλ(A)≤λ(id)per(A) is given.     

Row-ordering schemes for sparse givens transformations. I. bipartite graph model

Let A be an m-by-n matrix, m?n, and let P_r and P_c be permutation matrices of order m and n respectively. Suppose P_rAP_c is reduced to upper trapezoidal form $\text{(}\text{R}\text{O}\text{)}$ using Givens rotations, where R is n by n and upper triangular. The sparsity structure of R depends only on P_c. For a fixed P_c, the number of arithmetic operations required to compute R depends on P_r. In this paper, we consider row-ordering strategies which are appropriate when P_c is obtained from nested-dissection orderings of A^TA. Recently, it was shown that so-called “width-2” nested-dissection orderings of A^TA could be used to simultaneously obtain good row and column orderings for A. In this series of papers, we show that the conventional (width-1) nested-dissection orderings can also be used to induce good row orderings. In this first paper, we analyze the application of Givens rotations to a sparse matrix A using a bipartite-graph model.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Reducibility of the families of 0-dimensional schemes on a variety

IfA is a regular local ring of dimensionr>2, over an algebraically closed fieldk, we show that the Hilbert scheme Hilb ⁿ A parametrizing ideals of colengthn inA(dim _k A/I=n) has dimension>cn ^2?2/r and is reducible, for alln>c′, wherec andc′ depend only onr. We conclude that ifV is a nonsingular projective variety of dimensionr>2, the Hilbert scheme Hilb ⁿ V parametrizing the 0-dimensional subschemes ofV having lengthn, is reducible for alln>c″(r). We may takec″(r) to be (1) $$102 ifr = 3,25 ifr = 4,35 ifr = 5,and\left( {1 + r} \right)\left( {{{1 + r} \mathord{\left/ {\vphantom {{1 + r} 4}} \right. \kern-\nulldelimiterspace} 4}} \right)ifr > 5.$$ The result answers in the negative a conjecture of Fogarty [1] but leaves open the question of the conjectured irreducibility of Hilb ⁿ A, whereA has dimension 2. Hilb ⁿ V is known to be irreducible ifV is a nonsingular surface (Hartshorne forP ₂, and Fogarty [1]). In all cases Hilb ⁿ V and Hilb ⁿ A are known to be connected (Hartshorne forP _r, and Fogarty [1]). The author is indebted to Hartshorne for suggesting that Hilb ⁿ A might be reducible ifr>2. The proof has 3 steps. We first show that ifV is a variety of dimensionr, then Hilb ⁿ V is irreducible only if it has dimensionr n. We then show that ifA is a regular local ring of dimensionr, Hilb ⁿ A can be irreducible only if it has dimension (r?1)(n?1). Finally in § 3 we construct a family of graded ideals of colengthn in the local ringA, and having dimensionc′ n^2?2/r. Since for largen this dimension is greater thanr n, and since Hilb ⁿ A?Hilb ⁿ V whenA is the local ring of a closed point onV, the proof is complete, except for (1), which follows from § 3, and the monotonicity of (dim Hilb ⁿ V?r n) (see (2)). In § 4, we comment on some related questions.     

On a Conjecture of E. Dittert

Let K_n denote the set of all n X n nonnegative matrices whose entries have sum n, and let φ be a real valued function defined on K_n by φ(X) = π_iⁿ⁼¹ n, + π_j=1^c_j⁻ⁿ per X for X E K_n with row sum vector (r₁,…, r_n) and column sum vector (c_l,hellip;, c_n). For the same X, let φ_ij(X)= π_k≠ir_k + π_1≠jc₁ - per X(i| j). A ϵK_n is called a φ-maximizing matrix if φ(A) > φ(X) for all X ϵ K_n. Dittert's conjecture asserts that J_n = [1/n]_n×n is the unique (φ-maximizing matrix on K_n. In this paper, the following are proved: (i) If A = [a_ij] is a φ-maximizing matrix on K_n then φ_ij(A) = φ (A) if a_ij > 0, and φ_ij (A) ⩽ φ (A)if aij = 0. (ii) The conjecture is true for n = 3.     

Null ideals and spanning ranks of matrices

Let Rbe a commutative ring and A?M _m×n . The spanning rank of Ais the smallest positive integer s for which A=PQ(m×s s×n) The spanning rank of the zero matrix is set equal to zero. If Ris a field, then the spanning rank of Ais just the classical rank of A. In the first section of this paper, various theorems and examples are given which indicate how much of the classical theory of rank is still valid for spanning rank over a commutative ring. If A= PQ(n×s s×n) is a spanning rank factorization of a square matrix and D= QP, then Dis called a spanning rank partner of A. In the second part of this paper, the null ideals N _Aand N _Dof Aand Drespectively are compared. For instance, we show N _A=N _Dif s= nand N _A= XN _Dif s<nwhenever Ris a PIDand A≠0. This result sometimes (e.g. s<<n) makes the computation of N _Aeasy.     

Absolutely indecomposable symmetric matrices

Let A be a symmetric matrix of size n×n with entries in some (commutative) field K. We study the possibility of decomposing A into two blocks by conjugation by an orthogonal matrix T∈Mat_n(K). We say that A is absolutely indecomposable if it is indecomposable over every extension of the base field. If K is formally real then every symmetric matrix A diagonalizes orthogonally over the real closure of K. Assume that K is a not formally real and of level s. We prove that in Mat_n(K) there exist symmetric, absolutely indecomposable matrices iff n is congruent to 0, 1 or −1 modulo 2s.     

The additive and logical complexities of linear and bilinear arithmetic algorithms

Let C_A(±) be the additive complexity of a (bi)linear algorithm A for a given problem; D(A) and $\text{D}\text{(A)}$ are two acyclic diagraphs that represent A, each of them is obtained from another one by reversing directions of all edges; ir(D) and do(D) are two numbers that are introduced to measure the structural deficiencies of an acyclic digraph D. K and Q are the numbers of outputs and input-variables. $\text{do(}\text{D}\text{(A))}$, do(D(A)), and ir(D(A)) characterize the logical complexity of A. It is shown that C_A(±) + do(D(A)) + ir(D(A)) = ω(K + Q)log(K + Q) and $\text{C}{}_{\mathrm{A}}\text{(±) + do(}\text{D}\text{(A)) = ω(K + Q)}\text{log}\text{(K + Q)}$ in the cases of DFT, vector convolution, and matrix multiplication. Also lower bounds on C_A(±) + do(D(A)) and on C_A(±) are expressed in terms of algebraic quantities such as the ranks of matrices and of multidimensional tensors associated with the problems.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

On convexity properties of the spectral radius of nonnegative matrices

Elementary matrix-theoretic proofs are given for the following well-known results: r(D) = max{Re λ : λ an eigenvalue of A + D} and s(D) = lnρ(e^DA) are convex. Here D is diagonal, A a nonnegative n × n matrix, and ρ the spectral radius.