Faces of faces of the tridiagonal Birkhoff polytope

The tridiagonal Birkhoff polytope, , is the set of real square matrices with nonnegative entries and all rows and columns sums equal to 1 that are tridiagonal. This polytope arises in many problems of enumerative combinatorics, statistics, combinatorial optimization, etc. In this paper, for a given a p-face of , we determine the number of faces of lower dimension that are contained in it and we discuss its nature. In fact, a 2-face of is a triangle or a quadrilateral and the cells can only be tetrahedrons, pentahedrons or hexahedrons.     

Further results on iterative methods for computing generalized inverses

In this paper, we reconsider the iterative method X_k=X_k−1+βY(I−AX_k−1), k=1,2,…,β∈C?{0} for computing the generalized inverse over Banach spaces or the generalized Drazin inverse a^d of a Banach algebra element a, reveal the intrinsic relationship between the convergence of such iterations and the existence of or a^d, and present the error bounds of the iterative methods for approximating or a^d. Moreover, we deduce some necessary and sufficient conditions for iterative convergence to or a^d.     

Preservers of spectral radius, numerical radius, or spectral norm of the sum on nonnegative matrices

Let be the set of entrywise nonnegative n×n matrices. Denote by r(A) the spectral radius (Perron root) of . Characterization is obtained for maps such that r(f(A)+f(B))=r(A+B) for all . In particular, it is shown that such a map has the form

     

Some equalities for estimations of variance components in a general linear model and its restricted and transformed models

For the unknown positive parameter σ² in a general linear model , the two commonly used estimations are the simple estimator (SE) and the minimum norm quadratic unbiased estimator (MINQUE). In this paper, we derive necessary and sufficient conditions for the equivalence of the SEs and MINQUEs of the variance component σ² in the original model ?, the restricted model , the transformed model , and the misspecified model .     

On diameter and inverse degree of a graph

The inverse degree r(G) of a finite graph G=(V,E) is defined as , where is the degree of vertex v. We establish inequalities concerning the sum of the diameter and the inverse degree of a graph which for the most part are tight. We also find upper bounds on the diameter of a graph in terms of its inverse degree for several important classes of graphs. For these classes, our results improve bounds by Erd?s et al. (1988) [5], and by Dankelmann et al. (2008) [4].     

Quartic, octic residues and Lucas sequences

Let be a prime and a,b∈Z with a²+b²≠p. Suppose p=x²+(a²+b²)y² for some integers x and y. In the paper we develop the calculation technique of quartic Jacobi symbols and use it to determine . As applications we obtain the congruences for modulo p and the criteria for (if ), where {Un} is the Lucas sequence given by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1). We also pose many conjectures concerning , or .     

On the computation of the jdeg of blowup algebras

For a graded algebra , its is a global degree that can be used to study issues of complexity of the normalization . Here some techniques grounded on Rees algebra theory are used to estimate . A closely related notion, of divisorial generation, is introduced to count numbers of generators of .     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

Solution of a nonsymmetric algebraic Riccati equation from a two-dimensional transport model

For the steady-state solution of an integral-differential equation from a two-dimensional model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation B^--XF^--F⁺X+XB⁺X=0, where , and with a nonnegative matrix P, positive diagonal matrices D^±, and nonnegative parameters f, and . We prove the existence of the minimal nonnegative solution X^∗ under the physically reasonable assumption , and study its numerical computation by fixed-point iteration, Newton’s method and doubling. We shall also study several special cases; e.g. when and P is low-ranked, then is low-ranked and can be computed using more efficient iterative processes in U and V. Numerical examples will be given to illustrate our theoretical results.     

The Dirichlet Markov Ensemble

We equip the polytope of n×n Markov matrices with the normalized trace of the Lebesgue measure of Rⁿ². This probability space provides random Markov matrices, with i.i.d. rows following the Dirichlet distribution of mean (1/n,…,1/n). We show that if is such a random matrix, then the empirical distribution built from the singular values of tends as n→∞ to a Wigner quarter-circle distribution. Some computer simulations reveal striking asymptotic spectral properties of such random matrices, still waiting for a rigorous mathematical analysis. In particular, we believe that with probability one, the empirical distribution of the complex spectrum of tends as n→∞ to the uniform distribution on the unit disc of the complex plane, and that moreover, the spectral gap of is of order when n is large.     

Vanishing of derived limits of non-standard inverse systems

It is proved that for certain non-standard versions of inverse systems G of R-modules, we have for n>0.The result is applied to define a reasonably canonical non-standard resolution for an arbitrary inverse system G of R-modules, such that the application of the inverse limit functor yields a complex whose cohomology groups are isomorphic to the derived limits, limn. Furthermore, the non-standard resolution gives also the maps limng, and the connecting homomorphisms to a reasonable degree.We also prove that for miscellaneous types of inverse systems H of modules, the system H is a direct summand of .     

Exact rates in log law for positively associated random variables

Let be a strictly stationary sequence of positively associated random variables with mean zero and finite variance. Set , Mn=maxk?n|Sk|, n?1. Suppose . In this paper, we study the exact convergence rates of a kind of weighted infinite series of , and as ε↘0, respectively.     

Semilinear ordinary differential equation coupled with distributed order fractional differential equation

The system , where D^γ,γ∈[0,2] are operators of fractional differentiation, is investigated and the existence of a mild and classical solution is proven. Also, a necessary and sufficient condition for the existence and uniqueness of a solution to a general linear fractional differential equation , in is given.     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Singular-value-like decomposition for complex matrix triples

The classical singular value decomposition for a matrix A∈C^m×n is a canonical form for A that also displays the eigenvalues of the Hermitian matrices AA^∗ and A^∗A. In this paper, we develop a corresponding decomposition for A that provides the Jordan canonical forms for the complex symmetric matrices and . More generally, we consider the matrix triple , where are invertible and either complex symmetric or complex skew-symmetric, and we provide a canonical form under transformations of the form , where X,Y are nonsingular.     

Critical points between varieties generated by subspace lattices of vector spaces

We denote by the semilattice of all compact congruences of an algebra A. Given a variety V of algebras, we denote by the class of all semilattices isomorphic to for some A∈V. Given varieties V and W of algebras, the critical point of V under W is defined as . Given a finitely generated variety V of modular lattices, we obtain an integer ?, depending on V, such that for any n≥? and any field F.In a second part, using tools introduced in Gillibert (2009) [5], we prove that:

     

A classification of sharp tridiagonal pairs

Let F denote a field and let V denote a vector space over F with finite positive dimension. We consider a pair of linear transformations A:V→V and A^∗:V→V that satisfy the following conditions: (i) each of A,A^∗ is diagonalizable; (ii) there exists an ordering of the eigenspaces of A such that A^∗V_i⊆V_i-1+V_i+V_i+1 for 0?i?d, where V_-1=0 and V_d+1=0; (iii) there exists an ordering of the eigenspaces of A^∗ such that for 0?i?δ, where and ; (iv) there is no subspace W of V such that AW⊆W, A^∗W⊆W, W≠0, W≠V. We call such a pair a tridiagonal pair on V. It is known that d=δ and for 0?i?d the dimensions of coincide. The pair A,A^∗ is called sharp whenever . It is known that if F is algebraically closed then A,A^∗ is sharp. In this paper we classify up to isomorphism the sharp tridiagonal pairs. As a corollary, we classify up to isomorphism the tridiagonal pairs over an algebraically closed field. We obtain these classifications by proving the μ-conjecture.     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

Higher Kurtz randomness

A real x is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.