A q-analogue of the Riordan group

The Riordan group consisting of Riordan matrices shows up naturally in a variety of combinatorial settings. In this paper, we define a q-Riordan matrix to be a q  -analogue of the (exponential) Riordan matrix by using the Eulerian generating functions of the form _∑n?0fnzⁿ/n_!q${\sum }_{n?0}{f}_n{z}^n/n{!}_q$. We first prove that the set of q-Riordan matrices forms a loop (a quasigroup with an identity element) and find its loop structures. Next, it is shown that q-Riordan matrices associated to the counting functions may be applied to the enumeration problem on set partitions by block inversions. This notion leads us to find q-analogues of the composition formula and the exponential formula, respectively.     

Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffians

The classic Cayley identity states that

det(∂)(detX)^s=s(s+1)?(s+n−1)(detX)^s−1$\det (\partial ){(\det X)}^s=s(s+1)?(s+n-1){(\det X)}^{s-1}$

where X=(_xij)$X=(x_{ij})$ is an n×n$n\times n$ matrix of indeterminates and ∂=(∂/∂_xij)$\partial =(\partial /\partial x_{ij})$ is the corresponding matrix of partial derivatives. In this paper we present straightforward algebraic/combinatorial proofs of a variety of Cayley-type identities, both old and new. The most powerful of these proofs employ Grassmann algebra (= exterior algebra) and Grassmann–Berezin integration. Among the new identities proven here are a pair of “diagonal-parametrized” Cayley identities, a pair of “Laplacian-parametrized” Cayley identities, and the “product-parametrized” and “border-parametrized” rectangular Cayley identities.     

Analysis of symmetric matrix valued functions I

For any symmetric function f:Rⁿ?Rⁿ$f:{\mathbb{R}}^n?{\mathbb{R}}^n$, one can define a corresponding function on the space of n×n$n\times n$ real symmetric matrices by applying f$f$ to the eigenvalues of the spectral decomposition. We show that this matrix valued function inherits from f$f$ the properties of continuity, Lipschitz continuity, strict continuity, directional differentiability, Frechet differentiability, continuous differentiability.     

Generalized cover ideals and the persistence property

Let I   be a square-free monomial ideal in R=k[_x1,…,_xn]$R=k[x_1,\dots ,x_n]$, and consider the sets of associated primes Ass(I^s)$\mathrm{Ass}(I^s)$ for all integers s?1$s?1$. Although it is known that the sets of associated primes of powers of I eventually stabilize, there are few results about the power at which this stabilization occurs (known as the index of stability). We introduce a family of square-free monomial ideals that can be associated to a finite simple graph G that generalizes the cover ideal construction. When G   is a tree, we explicitly determine Ass(I^s)$\mathrm{Ass}(I^s)$ for all s?1$s?1$. As consequences, not only can we compute the index of stability, we can also show that this family of ideals has the persistence property.     

Depths and Cohen–Macaulay properties of path ideals

Given a tree T on n vertices, there is an associated ideal I   of R[_x1,…,_xn]$R[x_1,\dots ,x_n]$ generated by all paths of a fixed length ? of T  . We classify all trees for which R/I$R/I$ is Cohen–Macaulay, and we show that an ideal I whose generators correspond to any collection of subtrees of T satisfies the König property. Since the edge ideal of a simplicial tree has this form, this generalizes a result of Faridi. Moreover, every square-free monomial ideal can be represented (non-uniquely) as a subtree ideal of a graph, so this construction provides a new combinatorial tool for studying square-free monomial ideals.     

The inverse inertia problem for the complements of partial k-trees

Let F$\mathbb{F}$ be an infinite field with characteristic not equal to two. For a graph G=(V,E)$G=(V,E)$ with V={1,…,n}$V=\{1,\dots ,n\}$, let S(G;F)$S(G;\mathbb{F})$ be the set of all symmetric n×n$n\times n$ matrices A=[_ai,j]$A=[a_{i,j}]$ over F$\mathbb{F}$ with _ai,j≠0$a_{i,j}\ne 0$, i≠j$i\ne j$ if and only if ij∈E$ij\in E$. We show that if G is the complement of a partial k  -tree and m?k+2$m?k+2$, then for all nonsingular symmetric m×m$m\times m$ matrices K   over F$\mathbb{F}$, there exists an m×n$m\times n$ matrix U   such that U^TKU∈S(G;F)$U^{T}KU\in S(G;\mathbb{F})$. As a corollary we obtain that, if k+2?m?n$k+2?m?n$ and G is the complement of a partial k-tree, then for any two nonnegative integers p and q   with p+q=m$p+q=m$, there exists a matrix in S(G;R)$S(G;\mathbb{R})$ with p positive and q negative eigenvalues.     

On minors of the compound matrix of a Laplacian

Let L   be an n×n$n\times n$ matrix with zero row and column sums, n?3$n?3$. We obtain a formula for any minor of the (n−2)$(n-2)$-th compound of L. An application to counting spanning trees extending a given forest is given.     

Log-convexity and strong q-log-convexity for some triangular arrays

We give a criterion for the log-convexity (resp. the strong q  -log-convexity) of the first column of certain infinite triangular array _(An,k)0?k?n${(A_{n,k})}_{0?k?n}$ of nonnegative numbers (resp. of polynomials in q with nonnegative coefficients), for which the recurrence relation is of the form

_An,k=_{fkAn−1,k−1}+_gkAn−1,k+_hkAn−1,k+1.$A_{n,k}=f_k{A}_{n-1,k-1}+g_k{A}_{n-1,k}+h_k{A}_{n-1,k+1}.$

This allows a unified treatment of the log-convexity of the Catalan-like numbers, as well as that of the q-log-convexity of some classical polynomials. In particular, we obtain simple proofs of the q-log-convexity of Narayana polynomials.     

Circulant partial Hadamard matrices

A question arising in stream cypher cryptanalysis is reframed and generalized in the setting of Hadamard matrices as follows: For given n, what is the maximum value of k   for which there exists a k×n$k\times n$(±1)$(\pm 1)$-matrix A   such that AA^T=n_Ik$A{A}^{\mathsf{T}}=n{I}_k$, with each row after the first obtained by a cyclic shift of its predecessor by one position? For obvious reasons we call such matrices circulant partial Hadamard matrices. Further, what is the maximum value of k subject to the condition that the row sums are equal to r?     

On Mann iteration in Hilbert spaces

Let K$K$ be a compact convex subset of a real Hilbert space H$H$; T:K→K$T:K\to K$ a hemicontractive map. Let {_αn}$\left\{{\alpha }_n\right\}$ be a real sequence in [0,1] satisfying appropriate conditions; then for arbitrary _x0∈K$x_0\in K$, the sequence {_xn}$\left\{x_n\right\}$ defined iteratively by _xn=_αnxn−1+(1−_αn)T_xn$x_n={\alpha }_n{x}_{n-1}+(1-{\alpha }_n)T{x}_n$, n≥1$n\ge 1$ converges strongly to a fixed point of T$T$.     

On oriented graphs whose skew spectral radii do not exceed 2

Let S(G^σ)$S(G^{\sigma })$ be the skew adjacency matrix of the oriented graph G^σ$G^{\sigma }$ of order n   and _λ1,_λ2,…,_λn${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be all eigenvalues of S(G^σ)$S(G^{\sigma })$. The skew spectral radius _ρs(G^σ)${\rho }_s(G^{\sigma })$ of G^σ$G^{\sigma }$ is defined as max{|_λ1|,|_λ2|,…,|_λn|}$\max \{|{\lambda }_1|,|{\lambda }_2|,\dots ,|{\lambda }_n|\}$. In this paper, we investigate oriented graphs whose skew spectral radii do not exceed 2.     

Linear subspaces,symbolic powers and Nagata type conjectures

Inspired by results of Guardo, Van Tuyl and the second author for lines in P³${\mathbb{P}}^3$, we develop asymptotic upper bounds for the least degree of a homogeneous form vanishing to order at least m on a union of disjoint r  -dimensional planes in Pⁿ${\mathbb{P}}^n$ for n?2r+1$n?2r+1$. These considerations lead to new conjectures that suggest that the well known conjecture of Nagata for points in P²${\mathbb{P}}^2$ is not an exotic statement but rather a manifestation of a much more general phenomenon which seems to have been overlooked so far.     

The smallest regular polytopes of given rank

An abstract polytope is called regular   if its automorphism group has a single orbit on flags (maximal chains). In this paper, the regular n$n$-polytopes with the smallest number of flags are found, for every rank n>1$n>1$. With a few small exceptions, the smallest regular n$n$-polytopes come from a family of ‘tight’ polytopes with 2⋅4ⁿ⁻¹$2\cdot 4^{n-1}$ flags, one for each n$n$, with Schläfli symbol {4∣4∣?∣4}$\{4\mid 4\mid ?\mid 4\}$. Also with few exceptions, these have both the smallest number of elements, and the smallest number of edges in their Hasse diagram.     

Discrete Tomography and plane partitions

A plane partition   is a p×q$p\times q$ matrix A=(_aij)$A=(a_{ij})$, where 1?i?p$1?i?p$ and 1?j?q$1?j?q$, with non-negative integer entries, and whose rows and columns are weakly decreasing. From a geometric point of view plane partitions are equivalent to pyramids  , subsets of the integer lattice Z³${\mathbb{Z}}^3$ which play an important role in Discrete Tomography. As a consequence, some typical problems concerning the tomography of discrete lattice sets can be rephrased and considered via plane partitions. In this paper we focus on some of them. In particular, we get a necessary and sufficient condition for additivity, a canonical procedure for checking the existence of (weakly) bad configurations, and an algorithm which constructs minimal pyramids (with respect to the number of levels) with assigned projection of a bad configurations.     

Star-generating vectors of Rudin's quotient modules

The purpose of this paper is to study a class of quotient modules of the Hardy module H²(Dⁿ)$H^2({\mathbb{D}}^n)$. Along with the two variables quotient modules introduced by W. Rudin, we introduce and study a large class of quotient modules, namely Rudin's quotient modules of H²(Dⁿ)$H^2({\mathbb{D}}^n)$. By exploiting the structure of minimal representations we obtain an explicit co-rank formula for Rudin's quotient modules.