Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

Decomposable bilinear numerical radii

Let A be an n-square normal matrix over $\text{C}$, and Q_{m, n} be the set of strictly increasing integer sequences of length m chosen from 1,…, n. For α,β∈Q_{m, n} denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k∈{0,1,…,m} write z.sfnc;α∩β|=k if there exists a rearrangement of 1,…,m, say i₁,…,i_k, i_k+1,…,i_m, such that α(i_j)=β(i_j), j=1,…,k, and {α(i_k+1),…,α(i_m)};∩{β(i_k+1),…,β(i_m)}=ø. Let

be the group of n-square unitary matrices. Define the nonnegative number

$\text{?}{}_{\mathrm{k}}\text{(A)=}\text{max}\text{U∈}\textcolor{red}{}\text{|}\text{det}\text{(U}{}^1\text{AU) [α|β]|}$

, where |α∩β|=k. Theorem 1 establishes a bound for ?_k(A), 0?k<m?1, in terms of a classical variational inequality due to Fermat. Let A be positive semidefinite Hermitian, n?2m. Theorem 2 leads to an interlacing inequality which, in the case n=4, m=2, resolves in the affirmative the conjecture that

$\text{?}{}_{\mathrm{m}}\text{(A)??}{}_{\mathrm{m?1}}\text{(A)????}{}_0\text{(A)}$

.     

Independence numbers of graphs-an extension of the Koenig-Egervary theorem

Let G be an arbitrary finite, undirected graph with no loops nor multiple edges. In this paper the inequality β₀?n ? β₁ is investigated where β₀ is the independence number of G, n is the number of vertices, and β₁ is the cardinality of a maximum edge matching. The class of graphs for which equality holds is characterized. A polynomially-bounded algorithm is given which tests an arbitrary graph G for equality, and computes a maximum independent set of vertices when equality holds. Equality is “prevented” by the existence of a blossom-pair-a subgraph generated by a certain subset m_i of edges from a maximum edge matching M for G. It is shown that β₀ = n ?β₁?|R| where R is a minimum set oof representatives of the family {m_i} of blossom pair-generating subsets of M. Finally, apolynomially-bonded algorithm is given which partitions an arbitrary graph G into subgraphs G₀, G₁,…, G_q such that $\text{β}{}_0\text{(G) =}\text{∑}\text{i=0}\text{q}\text{β}{}_0\text{(G}{}_{\mathrm{i}}\text{)}$. Moreover, if arbitrary maximum independent subsets of vertices S₁, S₂,…, S_q are known, then a polynomially-bounded algorithm computes a maximum independent set S₀ for G₀ such that S=∪{S_i; i=0, 1,hellip;,q} is a maximum independent subset for G.     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

The asymptotic ruin problem when the healthy and sick periods form an alternating renewal process

Let {T₁, Y₁}^∞_i=1 be a sequence of positive independent random variables. Let, also, Z₁ = βY′₁ ? πT_i, i = 1, 2, …, where Y′₁ = Max(0, Y_i ? w), w ? 0, and where β < 0 and π is such that E(Z₁) < 0. We consider the random walk of partial sums S_n = ?ⁿ_i=1Z_i in the presence of an absorbing region (u, ∞), u ? 0, and S₀ ≡ 0. Of interest is $\text{ψ(u) = Pr(}\text{S}\text{?}\text{≤ u)}$ where S? = Sup(0, S₁, S₂, …, S_n, …).     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

Non-simply connected copes

Let (W⁴,?W⁴) be a 4-manifold. Let f₁,f₂,…,f_k:(D²,?D²)→ (W⁴,?W⁴) be transverse immersions that have spherical duals $\text{α}{}_1\text{,α}{}_2\text{,…,α}{}_{\mathrm{k}}\text{:S}{}^2\text{→}\text{W}\text{?}$. Then there are open disjoint subsets V₁, V₂,…,V_k of W, such that for each 1?i?k, (a) ?V_i=V₁∩?W and ?V_i is an open regular neighborhood of f_i(?D²) in ?W, and (b) (V_i,?V_i,f_i(?D²)) is proper homotopy equivalent to (M, ?M, d)—a standard object in which d bounds an embedded flat disk. If we could get a homeomorphism instead of a proper homotopy equivalence, then we would be able to prove a 5-dimensional s-cobordism theorem.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

Diagonal norm hermitian matrices

If v is a norm on $\text{C}$ⁿ, let H(v) denote the set of all norm-Hermitians in $\text{C}$ⁿⁿ. Let S be a subset of the set of real diagonal matrices D. Then there exists a norm v such that S=H(v) (or S = H(v)∩D) if and only if S contains the identity and S is a subspace of D with a basis consisting of rational vectors. As a corollary, it is shown that, for a diagonable matrix h with distinct eigenvalues λ₁,…, λ_r, r?n, there is a norm v such that h ∈ H(v), but h^s?H(v), for some integer s, if and only if λ₂–λ₁,…, λ_r–λ₁ are linearly dependent over the rationals. It is also shown that the set of all norms v, for which H(v) consists of all real multiples of the identity, is an open, dense subset, in a natural metric, of the set of all norms.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.     

On the irreducibility of multivariate subresultants

Let P₁,…,P_n be generic homogeneous polynomials in n variables of degrees d₁,…,d_n respectively. We prove that if ν is an integer satisfying ∑_i=1ⁿd_i?n+1?min{d_i}<ν, then all multivariate subresultants associated to the family P₁,…,P_n in degree ν are irreducible. We show that the lower bound is sharp. As a byproduct, we get a formula for computing the residual resultant of $\text{ρ?ν+n?1}\text{n?1}$ smooth isolated points in $\text{P}{}^{\mathrm{<mspace\; sp="0.2"\; width="2px"\; linebreak="nobreak"\; is="true"></mspace><mtext>n?1</mtext>}}\text{.}$To cite this article: L. Busé, C. D'Andrea, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

A characterization of planar cubic graphs

If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C₀, C₁,…, C_{n ? 1}, C₀ of the n circuits in S such that $\text{EC}{}_{\mathrm{i}}\text{? EC}{}_{\mathrm{j}}\text{≠ ?}$ if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties.     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

On a Question of Glasby,Praeger, and Xia

A Jordan partition λ(m, n, p) = (λ₁, λ₂, … , λ _m ) is a partition of mn associated with the expression of a tensor V _m  ? V _n of indecomposable KG-modules into a sum of indecomposables, where K is a field of characteristic p and G a cyclic group of p-power order. It is standard if λ _i  = m + n ? 2i + 1 for all i. We answer a recent question of Glasby, Praeger, and Xia who asked for necessary and sufficient conditions for λ(m, n, p) to be standard.