Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

APPLICATIONS OF CLIFFORD ALGEBRAS TO INVOLUTIONS AND QUADRATIC FORMS

ABSTRACT

Let k be a field, char k ≠ 2, F = k(x), D a biquaternion division algebra over k, and σ an orthogonal involution on D with nontrivial discriminant. We show that there exists a quadratic form ? ∈ I ²(F) such that dim ? = 8, [C(?)] = [D], and ? does not decompose into a direct sum of two forms similar to two-fold Pfister forms. This implies in particular that the field extension F(D)/F is not excellent. Also we prove that if A is a central simple K-algebra of degree 8 with an orthogonal involution σ, then σ is hyperbolic if and only if σ _K(A) is hyperbolic. Finally, let σ be a decomposable orthogonal involution on the algebra M _{2 ^m} (K). In the case m ≤ 5 we give another proof of the fact that σ is a Pfister involution. If m ≥ 2 ^n?2 ? 2 and n ≥ 5, we show that q _σ ∈ I ⁿ (K), where q _σ is a quadratic form corresponding to σ. The last statement is founded on a deep result of Orlov et al. (2000) concerning generic splittings of quadratic forms.     

A Tauberian theorem related to Weyl's criterion

Let {x_n} be a sequence of real numbers and let a(n) be a sequence of positive real numbers, with A(N) = Σ_n=1^Na(n). Tsuji has defined a notion of a(n)-uniform distribution mod 1 which is related to the problem of determining those real numbers t₀ for which A(N)^?1 Σ_n=1^Na(n)e^?it₀x_n → 0 as N → ∞. In case f(s) = Σ_n=1^∞a(n)e^?sx_n, s = σ + it, is analytic in the right half-plane 0 < σ, and satisfies a certain smoothness condition as σ → 0 +, we show that f(σ)^?1f(σ + it₀) → 0 as σ → 0 + if and only if A(N)^?1 Σ_n=1^Na(n)e^?it₀x_n → 0 as N → ∞.     

A perturbation analysis of the intrinsic conditioning of an approximate null vector computed with a SVD

Let A be an m ×n real matrix with singular values σ₁ ? ··· ? σ_n?1 ? σ_n ? 0. In cases where σ_n ? 0, the corresponding right singular vector υ_n is a natural choice to use for an approximate null vector ofA. Using an elementary perturbation analysis, we show that κ = σ₁/(σ_n?1 ? σ_n) provides a quantitative measure of the intrinsic conditioning of the computation of υ_n from A.     

Numerical solution of parameter‐dependent linear systems

We are interested in the numerical solution of the complex large linear system, (σ²A+σB+C)x=f(σ), for many, possibly a few hundreds, values of the complex parameter σ in a wide range. We assume that A, B and C are large, sparse, symmetric matrices, as is the case in several application problems. In particular, we focus on the following structured right‐hand side, f(σ)=FΦ(σ), where F is a (tall) rectangular matrix whose entries are independent of σ. We propose to approximate the solution x=x(σ) by means of a projection onto a single vector subspace, and a subsequent solution of the reduced dimension problem, for all values of interest of the parameter σ. Numerical experiments report the effectiveness of our approach on real application problems. Copyright © 2005 John Wiley & Sons, Ltd.     

Grassmannians of 2-Sided Vector Spaces

Let k ? K be an extension of fields, and let A ? M _n (K) be a k-algebra. We study parameter spaces of m-dimensional subspaces of K ⁿ which are invariant under A. The space  _A (m, n), whose R-rational points are A-invariant, free rank m summands of R ⁿ , is well known. We construct a distinct parameter space,  _A (m, n), which is a fiber product of a Grassmannian and the projectivization of a vector space. We then study the intersection  _A (m, n) ∩  _A (m, n), which we denote by  _A (m, n). Under suitable hypotheses on A, we construct affine open subschemes of  _A (m, n) and  _A (m, n) which cover their K-rational points. We conclude by using  _A (m, n),  _A (m, n), and  _A (m, n) to construct parameter spaces of 2-sided subspaces of 2-sided vector spaces.     

On the convex hull of the multiform numerical range

Let A ₁,…,A_m be nxn hermitian matrices. Definine

W(A ₁,…,A_m )={(xA₁x ^?,…xA_mx ^?):x?C ⁿ ,xx ^?=1}. We will show that every point in the convex hull of W(A ₁,…,A_m ) can be represented as a convex combination of not more than k(m,n) points in W(A ₁,…,A_m ) where k(m,n)=min{n,[√m]+δ _n ² _m+1}.     

Probabilistic Analysis of Condition Numbers for Linear Programming

In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C _R(A) introduced by Renegar (Ref. 2).     

The singular values of the hadamard product of a positive semidefinite and a skew-symmetric matrix

Let σ₁(X)≤ · ≤ σ_N(X)≤0 denote the ordered singular values ofan n × n matrix X and let α₁ (X) ≤ α₂(X)≤ · ≤ α_n(X) denote its ordered main diagonal entries (assuming that they are real). Let B be any complex n × n skew-symmetric matrix and ||.|| any unitarily invariant norm. It is shown that for any rea positive semidefinite n × n matrix A.     

Oscillation in the initial segment complexity of random reals

We study oscillation in the prefix-free complexity of initial segments of 1-random reals. For upward oscillations, we prove that _∑n∈ω²−g(n) diverges iff (^∃∞n)K(X?n)>n+g(n) for every 1-random X∈ω². For downward oscillations, we characterize the functions g such that (^∃∞n)K(X?n)<n+g(n) for almost every X∈ω². The proof of this result uses an improvement of Chaitin's counting theorem—we give a tight upper bound on the number of strings σ∈n² such that K(σ)<n+K(n)−m.The work on upward oscillations has applications to the K-degrees. Write XK_?Y to mean that K(X?n)?K(Y?n)+O(1). The induced structure is called the K-degrees. We prove that there are comparable () 1-random K-degrees. We also prove that every lower cone and some upper cones in the 1-random K-degrees have size continuum.Finally, we show that it is independent of ZFC, even assuming that the Continuum Hypothesis fails, whether all chains of 1-random K-degrees of size less than ℵ₀² have a lower bound in the 1-random K-degrees.     

Construction of nonnegative matrices and the inverse eigenvalue problem

This article presents a technique for combining two matrices, an n?×?n matrix M and an m?×?m matrix B, with known spectra to create an (n?+?m???p)?×?(n?+?m???p) matrix N whose spectrum consists of the spectrum of the matrix M and m???p eigenvalues of the matrix B. Conditions are given when the matrix N obtained in this construction is nonnegative. Finally, these observations are used to obtain several results on how to construct a realizable list of n?+?1 complex numbers (λ₁,λ₂,λ₃,σ) from a given realizable list of n complex numbers (c ₁,c ₂,σ), where c ₁ is the Perron eigenvalue, c ₂ is a real number and σ is a list of n???2 complex numbers.     

Enumeration of finite topologies

Let T₀(n) be the number of marked topologies satisfying the separation axiom T₀ that can be imposed on a finite set of n elements. In this paper the formula $$T_0 \left( n \right) = \Sigma \frac{{n!}}{{p_1 !...p_m !}}V\left( {p_1 , ..., p_m } \right)$$ is obtained, where the summation extends over all ordered sets of natural numbers (p₁, ..., p_m) such that p₁+...+p_m=n, and V(p₁, ..., p_m) denotes the number of matrices σ=(σ_ij) of ordern with the following properties: 1) each of the entries σ_ij is either 0 or 1, and if σ_ij=1 andσ_ij=1, then σ_ij=1;2) if the matrix σ is partitioned into blocks of sizes p_ixp_j, then all blocks under the main diagonal are zero, all diagonal blocks are identity matrices, and in each column of any block situated above the main diagonal at least one entry is 1. Some properties of the values V(p₁, ..., p_m)are obtained; in particular, it is shown that all these values are odd. Formulas are obtained for V(P₁, ..., p_m) corresponding to the simplest sets (p₁, ..., P_m) needed to calculate T₀(n) for n?8 (without using a computer).     

A Class of Sparse Invertible Matrices and Their Use for Nonlinear Prediction of Nearly Periodic Time Series with Fixed Period

We introduce a class of sparse matrices U _m (A _{p 1} ) of order m by m, where m is a composite natural number, p ₁ is a divisor of m, and A _{p 1} is a set of nonzero real numbers of length p ₁. The construction of U _m (A _{p 1} ) is achieved by iteration, involving repetitive dilation operations and block-matrix operations. We prove that the matrices U _m (A _{p 1} ) are invertible and we compute the inverse matrix (U _m (A _{p 1} ))^?1 explicitly. We prove that each row of the inverse matrix (U _m (A _{p 1} ))^?1 has only two nonzero entries with alternative signs, located at specific positions, related to the divisors of m. We use the structural properties of the matrix (U _m (A _{p 1} ))^?1 in order to build a nonlinear estimator for prediction of nearly periodic time series of length m with fixed period.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Irreducibility of associated matrices

For an n by n matrix A, let K(A) be the associated matrix corresponding to a permutation group (of degree m) and one of its characters. Let D_r(A) be the coefficient of x^m?r in K(A+xI). If A is reducible, then D_r(A) is reducible. If A is irreducible and the character is identically one, then D₁(A) is irreducible. If A is row stochastic and the character is identically one, then D_r(A) is essentially row stochastic. Finally, the results motivate the definition of group induced diagraphs.     

Adjacency preserving functions on symmetric elements and linear preservers of non-zero decomposable symmetric tensors

Let A be a non-empty set and m be a positive integer. Let ≡ be the equivalence relation defined on A ^m such that (x ₁, …, x _m ) ≡ (y ₁, …, y _m ) if there exists a permutation σ on {1, …, m} such that y _σ(i) = x _i for all i. Let A ^(m) denote the set of all equivalence classes determined by ≡. Two elements X and Y in A ^(m) are said to be adjacent if (x ₁, …, x _m?1, a) ∈ X and (x ₁, …, x _m?1, b) ∈ Y for some x ₁, …, x _m?1 ∈ A and some distinct elements a, b ∈ A. We study the structure of functions from A ^(m) to B ⁽ⁿ⁾ that send adjacent elements to adjacent elements when A has at least n + 2 elements and its application to linear preservers of non-zero decomposable symmetric tensors.     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.     

PSC Galois Extensions of Hilbertian Fields

We prove the following result: Theorem. Let K be a countable Hilbertian field, S a finite set of local primes of K, and e ≥ 0 an integer. Then, for almost all σ ∈ G (K)^e, the field K_s [ σ ] ∩ K_tot,S is PSC. Here a local prime is an equivalent class 𝔭 of absolute values of K whose completion is a local field, _𝔭. Then K_𝔭 = K_s ∩ _𝔭 and K_tot,S = ∩_{𝔭 ∈ S}∩_{σ ∈ G(K)} K^σ_𝔭. G(K) stands for the absolute Galois group of K. For each σ = (σ₁, …, σ_e ) ∈ G(K)^e we denote the fixed field of σ₁, …, σ_e in K_s by K_s( σ ). The maximal Galois extension of K in K_s( σ ) is K_s[ σ ]. Finally “almost all” means “for all but a set of Haar measure zero”.     

Eulerian numbers,Newcomb's problem and representations of symmetric groups

Consider a set of n positive integers consisting of μ₁ 1's, μ₂ 2's,…, μ_rr's. If the integer in the ith place in an arrangement σ of this set is σ(i), and a non-rise in σ is defined as σ(i+1)?σ(i), a problem that suggests itself is the determination of the number of arrangements σ with k non-rises. When each μ_i is unity, the problem is that of finding the number A(n, k) of permutations of distinct integers 1, 2,…, n with k descents, a descent being defined as σ(i+1)<σ(i). The number A(n, k) is known as an Eulerian number. The problem of finding the number of arrangements with k non-rises of the more general set, when not all of μ_i are unity, has appeared in the literature as one part of a problem on dealing a pack of cards, this having been proposed by the American astronomer Simon Newcomb (1835–1909).Both the Eulerian numbers and Newcomb's problem have accumulated a substantial literature. The present paper considers these topics from an entirely new stand-point, that of representations of the symmetric group. This approach yields a well-known recurrence for the Eulerian numbers and a known formula for them in terms of Stirling numbers. It also gives the solutions of the Newcomb problem and some recurrences between these solutions, not all of which have been found earlier. A simple connection is found between Stirling numbers and the Kostka numbers of symmetric group representation theory. The Eulerian numbers can also be expressed in terms of the Kostka numbers.The idea which is novel in this treatment and recurs almost as a motif throughout the paper is that of a skew-hook. This occurs in the first place in a very natural way as a picture of the rises and non-rises of σ, with the nodes of the skew-hook labelled successively as σ(1), σ(2),…. As the paper develops, a new form of skew-hook associated with σ emerges. This does not in general depict the rises and non-rises of σ, and it is now the edges, not the nodes, which carry integer labels. A new type of combinatorial number, here called a ψ-function, arises from these edge-labelled skew-hooks. The ψ-functions are intimately related to the Eulerian numbers and the Newcomb solutions and may have further combinatorial applications. The skew-hook treatment casts fresh light on MacMahon's solution of the Newcomb problem and on his “new symmetric functions”, and, if σ(i)?σ(i+1)?s defines an s-descent in σ, on the enumeration of permutations with ks-descents.Also some characters of the symmetric group with interesting properties and recurrences arise in the course of the paper.