Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial identities related to $2times 2$ submatrices of recursive matrices
307
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Recursive matrices are ubiquitous in combinatorics, which have been extensively studied. We focus on the study of the sums of $2times 2$ minors of certain recursive matrices, the alternating sums of their $2times 2$ minors, and the sums of their $2times 2$ permanents. We obtain some combinatorial identities related to these sums, which generalized the work of Sun and Ma in [{it Electron. J. Combin. 2014}] and [{it European J. Combin. 2014}]. With the help of the computer algebra package {tt HolonomicFunctions}, we further get some new identities involving Narayana polynomials.
rate research
Read More
Let $Q_{n,d}$ denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in ${0,1}^n$ having precisely $d$ entries equal to $1$. We present a short proof of the fact that $Pr[det(Q_{n,d})=0] = Oleft(frac{n^{1/2}log^{3/2} n}{d}right)=o(1)$, whenever $d=omega(n^{1/2}log^{3/2} n)$. In particular, our proof accommodates sparse random combinatorial matrices in the sense that $d = o(n)$ is allowed. We also consider the singularity of deterministic integer matrices $A$ randomly perturbed by a sparse combinatorial matrix. In particular, we prove that $Pr[det(A+Q_{n,d})=0]=Oleft(frac{n^{1/2}log^{3/2} n}{d}right)$, again, whenever $d=omega(n^{1/2}log^{3/2} n)$ and $A$ has the property that $(1,-d)$ is not an eigenpair of $A$.
The main result of this paper is the decidability of the membership problem for $2times 2$ nonsingular integer matrices. Namely, we will construct the first algorithm that for any nonsingular $2times 2$ integer matrices $M_1,dots,M_n$ and $M$ decides whether $M$ belongs to the semigroup generated by ${M_1,dots,M_n}$. Our algorithm relies on a translation of the numerical problem on matrices into combinatorial problems on words. It also makes use of some algebraical properties of well-known subgroups of $mathrm{GL}(2,mathbb{Z})$ and various new techniques and constructions that help to limit an infinite number of possibilities by reducing them to the membership problem for regular languages.
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn/2k)^2 . Using this result we derive the following applications: (1) Impossibility results for 2-query LCCs over the complex numbers: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over the complex numbers. (2) Generalization of results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let $v_1,...,v_m$ be a set of points in $C^d$ such that for every $i in [m]$ there exists at least $delta m$ values of $j in [m]$ such that the line through $v_i,v_j$ contains a third point in the set. We show that the dimension of ${v_1,...,v_m }$ is at most $O(1/delta^2)$. Our results generalize to the high dimensional case (replacing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
Let $mathcal S$ be a single condition Schubert variety with an arbitrary number of strata. Recently, an explicit description of the summands involved in the decomposition theorem applied to such a variety has been obtained in a paper of the second author. Starting from this result, we provide an explicit description of the Poincar{e} polynomials of the intersection cohomology of $mathcal S$ by means of the Poincar{e} polynomials of its strata, obtaining interesting polynomial identities relating Poincar{e} polynomials of several Grassmannians, both by a local and by a global point of view. We also present a symbolic study of a particular case of these identities.
In this paper we study products of quadratic residues modulo odd primes and prove some identities involving quadratic residues. For instance, let $p$ be an odd prime. We prove that if $pequiv5pmod8$, then $$prod_{0<x<p/2,(frac{x}{p})=1}xequiv(-1)^{1+r}pmod p,$$ where $(frac{cdot}{p})$ is the Legendre symbol and $r$ is the number of $4$-th power residues modulo $p$ in the interval $(0,p/2)$. Our work involves class number formula, quartic Gauss sums, Stickelbergers congruence and values of Dirichlet L-series at negative integers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
