Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Palindromic widths of nilpotent and wreath products

We prove that the nilpotent product of a set of groups A ₁,…,A _s has finite palindromic width if and only if the palindromic widths of A _i ,i=1,…,s,are finite. We give a new proof that the commutator width of F _n ?K is infinite, where F _n is a free group of rank n≥2 and K is a finite group. This result, combining with a result of Fink [9] gives examples of groups with infinite commutator width but finite palindromic width with respect to some generating set.     

An extended class of stabilizable uncertain systems

The system of equations \(\frac{{dx}}{{dt}} = A\left( \cdot \right)x + B\left( \cdot \right)u\), where A(·) ∈ ?^{n × n}, B(·) ∈ ?^{n × m}, S(·) ∈ R^{n × m}, is considered. The elements of the matrices A(·), B(·), S(·) are uniformly bounded and are functionals of an arbitrary nature. It is assumed that there exist k elements \({\alpha _{{i_i}{j_l}}}\left( \cdot \right)\left( {l \in \overline {1,k} } \right)\) of fixed sign above the main diagonal of the matrix A(·), and each of them is the only significant element in its row and column. The other elements above the main diagonal are sufficiently small. It is assumed that m = n ?k, and the elements β_ij(·) of the matrix B(·) possess the property \(\left| {{\beta _{{i_s}s}}\left( \cdot \right)} \right| = {\beta _0} > 0\;at\;{i_s}\; \in \;\overline {1,n} \backslash \left\{ {{i_1}, \ldots ,{i_k}} \right\}\). The other elements of the matrix B(·) are zero. The positive definite matrix H = {h_ij} of the following form is constructed. The main diagonal is occupied by the positive numbers h_ii = h_i, \({h_{{i_l}}}_{{j_l}}\, = \,{h_{{j_l}{i_l}}}\, = \, - 0.5\sqrt {{h_{{i_l}}}_{{j_l}}} \,\operatorname{sgn} \,{\alpha _{{i_l}}}_{{j_l}}\left( \cdot \right)\). The other elements of the matrix H are zero. The analysis of the derivative of the Lyapunov function V(x) = x*H^–1x yields h_i\(\left( {i \in \overline {1,n} } \right)\) and λ_i ≤ 0 \(\left( {i \in \overline {1,n} } \right)\) such that for S(·) = H^?1ΛB(·), Λ = diag(λ₁, ..., λ_n), the system of the considered equations becomes globally exponentially stable. The control is robust with respect to the elements of the matrix A(·).     

The real symmetric matrices of odd order with a P-set of maximum size

Suppose that A is a real symmetric matrix of order n. Denote by m_A(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_A(α)(0) = m_A(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most ?n/2? elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n ? 1)/2.     

Positivity Criteria Generalizing the Leading Principal Minors Criterion

An n×n Hermitian matrix is positive definite if and only if all leading principal minors Δ₁, . . . ,Δ_n are positive. We show that certain sums δ _l of l × l principal minors can be used instead of Δ _l in this criterion. We describe all suitable sums δ _l for 3 × 3 Hermitian matrices. For an n×n Hermitian matrix A partitioned into blocks A _ij with square diagonal blocks, we prove that A is positive definite if and only if the following numbers σ _l are positive: σ _l is the sum of all l × l principal minors that contain the leading block submatrix [A _ij ] ^{k ?1} _{i,j =1} (if k > 1) and that are contained in [A _ij ] ^k _{i,j =1}, where k is the index of the block A _kk containing the (l, l) diagonal entry of A. We also prove that σ _l can be used instead of Δ _l in other inertia problems.     

G-matrices,J-orthogonal matrices,and their sign patterns

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D₁ and D₂ such that A^?T = D₁AD₂, where A^?T denotes the transpose of the inverse of A. Denote by J = diag(±1) a diagonal (signature) matrix, each of whose diagonal entries is +1 or ?1. A nonsingular real matrix Q is called J-orthogonal if Q^TJQ = J. Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of a J-orthogonal matrix. An investigation into the sign patterns of the J-orthogonal matrices is initiated. It is observed that the sign patterns of the G-matrices are exactly the column permutations of the sign patterns of the J-orthogonal matrices. Some interesting constructions of certain J-orthogonal matrices are exhibited. It is shown that every symmetric staircase sign pattern matrix allows a J-orthogonal matrix. Sign potentially J-orthogonal conditions are also considered. Some examples and open questions are provided.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

Systems that generate solutions with a small period

Let (j₁,..., j_n) be a permutation of the n-tuple (1, ..., n). A system of differential equations \(\dot x = {f_i}\left( {{x_{{j_i}}}} \right),i = 1, \ldots ,n\) in which each function f_i is continuous on ? is considered. This system is said to have the property of generation of solutions with a small period if, for any number M > 0, there exists a number ω₀ = ω₀(M) > 0 such that if 0 < ω ≤ ω₀ and h_i(t, x₁, ..., x_n) are continuous functions on ? × ?ⁿ ω-periodic in t that satisfy the inequalities |h_i| ≤ M the system \(\dot x = {f_i}\left( {{x_{{j_i}}}} \right),i = 1, \ldots ,n\) has an ω-periodic solution. It is shown that a system has the property of generation of solutions with a small period if and only if f_i(?) = ? for i = 1,..., n. It is also shown that the smallness condition on the period is essential.     

Dn,r is not potentially nilpotent for n ⩾ 4r − 2

An n × n sign pattern A is said to be potentially nilpotent if there exists a nilpotent real matrix B with the same sign pattern as A. Let D_n,r be an n × n sign pattern with 2 ≤ r ≤ n such that the superdiagonal and the (n, n) entries are positive, the (i, 1) (i = 1,..., r) and (i, i ? r + 1) (i = r + 1,..., n) entries are negative, and zeros elsewhere. We prove that for r ≥ 3 and n ≥ 4r ? 2, the sign pattern D_n,r is not potentially nilpotent, and so not spectrally arbitrary.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).     

Semigroup and Metric Characteristics of Locally Primitive Matrices and Digraphs

The notion of local primitivity for a quadratic 0, 1-matrix of size n × n is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set B of pairs of initial and final vertices of the paths in an n-vertex digraph, B ? {(i, j) : 1 ≤ i, j ≤ n}. We establish the relationship between the local B-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotentmatrices in the multiplicative semigroup of all quadratic 0, 1-matrices of order n, etc. We obtain a criterion of B-primitivity and an upper bound for the B-exponent. We also introduce some new metric characteristics for a locally primitive digraph Γ: the k, r-exporadius, the k, r-expocenter, where 1 ≤ k, r ≤ n, and the matex which is defined as the matrix of order n of all local exponents in the digraph Γ. An example of computation of the matex is given for the n-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable s-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes.     

On Excess-time Correlated Cumulative Processes

In this paper a class of correlated cumulative processes, B _s (t) = ∑^N(t)_i=1 H _s (X _i )X _i , is studied with excess level increments X _i ?s, where {N(t), t ?0} is the counting process generated by the renewal sequence T _n , T _n and X _n are correlated for given n, H _s (t) is the Heaviside function and s?0 is a given constant. Several useful results, for the distributions of B _s (t), and that of the number of excess (non-excess) increments on (0, t) and the corresponding means, are derived. First passage time problems are also discussed and various asymptotic properties of the processes are obtained. Transform results, by applying a flexible form for the joint distribution of correlated pairs (T _n , X _n ) are derived and inverted. The case of non-excess level increments, X _i < s, is also considered. Finally, applications to known stochastic shock and pro-rata warranty models are given.     

Hyperbolic Chevalley groups on ℂ<Superscript>2</Superscript>

Let Γ ? U (1, 1) be the subgroup generated by the complex reflections. Suppose that Γ acts discretely on the domain K = {(z ₁, z ₂) ∈ ?² ||z ₁|² ? |z ₂|² < 0} and that the projective group PΓ acts on the unit disk B = {|z ₁/z ₂| < 1} as a Fuchsian group of signature (n ₁, ..., n _s ), s ? 3, n _i ? 2. For such groups, we prove a Chevalley type theorem, i.e., find a necessary and sufficient condition for the quotient space K/Γ to be isomorphic to ?² ? {0}.     

Stabilization of a Class of Uncertain Systems

We consider the problem to synthesize a stabilizing control u synthesis for systems \(\frac{{dx}}{{dt}} = Ax + Bu\) where A ∈ ?^n×n and B ∈ ?^n×m, while the elements α_i,j(·) of the matrix A are uniformly bounded nonanticipatory functionals of arbitrary nature. If the system is continuous, then the elements of the matrix B are continuous and uniformly bounded functionals as well. If the system is pulse-modulated, then the elements of the matrix B are differentiable uniformly bounded functions of time. It is assumed that k isolated uniformly bounded elements \({\alpha _{{i_l},{j_l}}}\left( \cdot \right)\) satisfying the condition \(\mathop {\inf }\limits_{\left( \cdot \right)} \left| {{\alpha _{{i_l},{j_l}}}\left( \cdot \right)} \right|{\alpha _ - } > 0,\quad l \in \overline {1,k}\) are located above the main diagonal of the matrix A(·), where G _k is the set of all isolated elements of the system, J₁ is the set of indices of rows of matrix A(·) containing isolated elements, and J₂ is the set of indices of its rows free of isolated elements. It is assumed that other elements located above the main diagonal are sufficiently small provided that their row indices belong to J₁, i.e., \(\mathop {\sup }\limits_{\left( \cdot \right)} \left| {{\alpha _{i,j}}\left( \cdot \right)} \right| < \delta ,\quad {\alpha _{i,j}} \notin {G_k},\quad i \in {J_1},\quad j > i\). All other elements located above the main diagonal are uniformly bounded. The relation u = S(·)x is satisfied in the continuous case, while the relation u = ξ(t) is satisfied in the pulse-modulated case; here the components of the vector ξ are outputs of synchronous pulse elements. Constructing a special quadratic Lyapunov function, one can determine a matrix S(·) such that the closed system becomes globally exponentially stable in the continuous case. In the pulse-modulated case, input pulses are synthesized such that the system becomes globally asymptotically stable.     

The SL(<Emphasis Type="Italic">V</Emphasis>)-ample cone of product of flag varieties

Let k be an algebraically closed field, and V be a vector space of dimension n over k. For a set ω = (\(\vec d\)(1), ..., \(\vec d\)(m)) of sequences of positive integers, denote by L _ω the ample line bundle corresponding to the polarization on the product X = Π _i=1 ^m Flag(V, \(\vec n\)(i)) of flag varieties of type \(\vec n\)(i) determined by ω. We study the SL(V)-linearization of the diagonal action of SL(V) on X with respect to L _ω. We give a sufficient and necessary condition on ω such that X ^ss (L _ω) ≠ \(\not 0\) (resp., X ^s (L _ω) ≠ \(\not 0\)). As a consequence, we characterize the SL(V)-ample cone (for the diagonal action of SL(V) on X), which turns out to be a polyhedral convex cone.     

Degeneracy of holomorphic curves in surfaces

LetX be a complex projective algebraic manifold of dimension 2 and let D₁, ..., D_u be distinct irreducible divisors onX such that no three of them share a common point. Let\(f:{\mathbb{C}} \to X\backslash ( \cup _{1 \leqslant i \leqslant u} D_i )\) be a holomorphic map. Assume thatu ? 4 and that there exist positive integers n₁, ... ,n_u,c such that n_in_J D _i.D_j) =c for all pairsi,j. Thenf is algebraically degenerate, i.e. its image is contained in an algebraic curve onX.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

On boundary value problems for systems of nonlinear generalized ordinary differential equations

A general theorem (principle of a priori boundedness) on solvability of the boundary value problem dx = dA(t) · f(t, x), h(x) = 0 is established, where f: [a, b]×R ⁿ → R ⁿ is a vector-function belonging to the Carathéodory class corresponding to the matrix-function A: [a, b] → R ^n×n with bounded total variation components, and h: BV_s([a, b],R ⁿ ) → R ⁿ is a continuous operator. Basing on the mentioned principle of a priori boundedness, effective criteria are obtained for the solvability of the system under the condition x(t₁(x)) = B(x) · x(t ₂(x))+c ₀, where t _i: BV_s([a, b],R ⁿ ) → [a, b] (i = 1, 2) and B: BV_s([a, b], R ⁿ ) → R ⁿ are continuous operators, and c ₀ ∈ R ⁿ .     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Extrapolation in Grand Lebesgue Spaces with <Emphasis Type="Italic">A</Emphasis>∞ Weights

Results on extrapolation withA∞ weights in grand Lebesgue spaces are obtained. Generally, these spaces are defined with respect to the productmeasure μ₁ ×· · ·×μ_n onX₁ ×· · ·×X_n, where (X_i, d_i, μ_i), i = 1,..., n, are spaces of homogeneous type. As applications of the obtained results, new one-weight estimates with A_∞ weights for operators of harmonic analysis are derived.