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.     

A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Matrices A for which the upper bound per(A)?1+min{Π(c_i?1), Π(r_i?1)} holds with equality are characterized. Cases where the bound is achieved correspond to multigraphs with the property that there exists a unique path from any vertex to any disjoint cycle union. This occurs precisely when some multigraph associated with A has the mastercycle property: all cycles thread all branchpoints in the same circular order. Such multigraphs may also be characterized as a circular concatenation of certain acyclic multigraphs, each having a unique source and sink. This analysis yields two normal forms for the extremal matrices, one based on a nested block decomposition, and another based on an overlapping block decomposition. The extremal cases are invariant under contractions, yielding another characterization.     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

Multiple cross-intersecting families of signed sets

A k-signed r-set on[n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A₁,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.     

Extremal Systems with Upper-Bounded Odd Intersections

In this paper we determine the maximum cardinality m of a family A= {A ₁,..., A _m} of subsets of a set of n elements with the property that for each A _i there are at most s A _j such that |A _i ∩ A _j | is odd (even). A tight upper bound is given in the case s < c(2 ^n,2/n). In the remaining cases we give an asymptotically tight upper bound. As an application we give a tight upper-bound for the cardinality of a family with even multi-intersection. Both results generalize a result of Berlekamp and Graver.     

Anti-Hadamard matrices

An anti-Hadamard matrix may be loosely defined as a real (0, 1) matrix which is invertible, but only just. Let A be an invertible (0, 1) matrix with eigenvalues λ_i, singular values σ_i, and inverse B = (b_ij). We are interested in the four closely related problems of finding λ(n) = min_{A, i}|λ_i|, σ(n) = min_{A, i}σ_i, χ(n) = max_{A, i, j} |b_ij|, and μ(n) = max_AΣ_ijb²_ij. Then A is an anti-Hadamard matrix if it attains μ(n). We show that λ(n), σ(n) are between $\text{(2n)}{}^{\mathrm{?1}}\text{(}\text{n}\text{4}\text{)}{}^{\mathrm{<mtext>?n</mtext><mtext>2</mtext>}}$ and c√n (2.274)^?n, where c is a constant, $\text{c}\text{(2.274)}{}^{\mathrm{n}}\text{?χ(n)?2(}\text{n}\text{4}\text{)}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}$, and $\text{c}\text{(5.172)}{}^{\mathrm{n}}\text{?μ(n)?4n}{}^2\text{(}\text{n}\text{4}\text{)}{}^{\mathrm{n}}$. We also consider these problems when A is restricted to be a Toeplitz, triangular, circulant, or (+1, ?1) matrix. Besides the obvious application—to finding the most ill-conditioned (0, 1) matrices—there are connections with weighing designs, number theory, and geometry.     

The characteristic polynomial of a principal subpencil of a Hermitian matrix pencil

Given n-square Hermitian matrices A,B, let A_i,B_i denote the principal (n?1)- square submatrices of A,B, respectively, obtained by deleting row i and column i. Let μ, λ be independent indeterminates. The first main result of this paper is the characterization (for fixed i) of the polynomials representable as det(μA_i?λB_i) in terms of the polynomial det(μA?λB) and the elementary divisors, minimal indices, and inertial signatures of the pencil μA?λB. This result contains, as a special case, the classical interlacing relationship governing the eigenvalues of a principal sub- matrix of a Hermitian matrix. The second main result is the determination of the number of different values of i to which the characterization just described can be simultaneously applied.     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.     

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.     

Partitions and sums of integers with repetition

A partition of N is called “admissible” provided some cell has arbitrarily long arithmetic progressions of even integers in a fixed increment. The principal result is that the statement “Whenever {A_i}_{i < r} is an admissible partition of N, there are some i < r and some sequence 〈x_n〉_{n < ω} of distinct members of N such that x_n + x_m?A_i whenever {m, n} ? ω″ is true when r = 2 and false when r ? 3.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

On separating systems whose elements are sets of at most k elements

A system A₁,…,A_m of subsets of X?{1,…,n} is called a separating system if for any two distinct elements of X there is a set A_i (1?i?m) that contains exactly one of the two elements. We investigate separating systems where each set A_i has at most k elements and we are looking for minimal separating systems, that means separating systems with the least number of subsets. We call this least number m(n,k). Katona has proved good bounds on m(n,k) but his proof is very complicated. We give a shorter and easier proof. In doing so we slightly improve the upper bound of Katona.     

Presentations of alternating semigroups

One presentation of the alternating groupA _n hasn?2 generatorss ₁,…,s_n?2 and relationss ₁ ³ =s _i ² =(s_1?1s_i)³=(s_js_k)²=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupA _n ^c )A _n is introduced: It hasn?1 generatorss ₁,…,S _n?2,e, theA _n-relations (above), and relationse ²=e, (es ₁)⁴, (es _j)²=(es _j)⁴,es _i=s _i s ₁ ^-1 es ₁, wherej>1 andi≥1.     

A note on matricial minimality

Let A be a complex n×n matrix, θ a matricial norm and r(A) the spectral radius of A. Then, it is known [2,7], r(A?r(θ(A)). In our present note we investigate when r(A?αI_n)=r(θ(A?αI_n))?α?C.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

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.     

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.     

Maximum modulus sets in pseudoconvex boundaries

LedD be a strictly pseudoconvex domain in ? ⁿ withC ^∞ boundary. We denote byA ^∞(D) the set of holomorphic functions inD that have aC ^∞ extension to \(\bar D\) . A closed subsetE of ?D is locally a maximum modulus set forA ^∞(D) if for everyp∈E there exists a neighborhoodU ofp andf∈A ^∞(D∩U) such that |f|=1 onE∩U and |f|<1 on \(\bar D \cap U\backslash E\) . A submanifoldM of ?D is an interpolation manifold ifT _p (M)?T _p ^c (?D) for everyp∈M, whereT _p ^c (?D) is the maximal complex subspace of the tangent spaceT _p (?D). We prove that a local maximum modulus set forA ^∞ (D) is locally contained in totally realn-dimensional submanifolds of ?D that admit a unique foliation by (n?1)-dimensional interpolation submanifolds. LetD =D ₁ x ... xD _r ? ? ⁿ whereD _i is a strictly pseudoconvex domain withC ^∞ boundary in ? ⁿ _i ,i=1,…,r. A submanifoldM of ?D ₁×…×?D _r verifies the cone condition if \(II_p (T_p (M)) \cap \bar C[Jn_1 (p),...,Jn_r (p)] = \{ 0\} \) for everyp∈M, wheren _i (p) is the outer normal toD _i atp, J is the complex structure of ? ⁿ , \(\bar C[Jn_1 (p),...,Jn_r (p)]\) is the closed positive cone of the real spaceV _p generated byJ _{n 1}(p),…,J _{n r}(p), and II _p is the orthogonal projection ofT _p (?D) onV _p . We prove that a closed subsetE of ?D ₁×…×?D _r which is locally a maximum modulus set forA ^∞(D) is locally contained inn-dimensional totally real submanifolds of ?D ₁×…×?D _r that admit a foliation by (n?1)-dimensional submanifolds such that each leaf verifies the cone condition at every point ofE. A characterization of the local peak subsets of ?D ₁×…×?D _r is also given.     

A general upper bound for 1-widths

Let A be an m × n(0, 1)-matrix having row sums ? r and column sums ? c. An upper bound for the 1-width of A is obtained in terms of m, n, r, c.