Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFooling-sets and rank in nonzero characteristic (extended abstract)
136
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An ntimes n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k e ell we have M_{k,ell} M_{ell,k} = 0. Dietzfelbinger, Hromkoviv{c}, and Schnitger (1996) showed that n le (rk M)^2, regardless of over which field the rank is computed, and asked whether the exponent on rk M can be improved. We settle this question for nonzero characteristic by constructing a family of matrices for which the bound is asymptotically tight. The construction uses linear recurring sequences.
rate research
Read More
An $ntimes n$ matrix $M$ is called a textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,ell} M_{ell,k} = 0$ for every $k e ell$. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that $n le (mbox{rk} M)^2$, regardless of over which field the rank is computed, and asked whether the exponent on $mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = binom{mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(mbox{rk} M)^2$.
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
In order theory, a rank function measures the vertical level of a poset element. It is an integer-valued function on a poset which increments with the covering relation, and is only available on a graded poset. Defining a vertical measure to an arbitrary finite poset can be accomplished by extending a rank function to be interval-valued. This establishes an order homomorphism from a base poset to a poset over real intervals, and a standard (canonical) specific interval rank function is available as an extreme case. Various ordering relations are available over intervals, and we begin in this paper by considering conjugate orders which partition the space of pairwise comparisons of order elements. For us, these elements are real intervals, and we consider the weak and subset interval orders as (near) conjugates. It is also natural to ask about interval rank functions applied reflexively on whatever poset of intervals we have chosen, and thereby a general iterative strategy for interval ranks. We explore the convergence properties of standard and conjugate interval ranks, and conclude with a discussion of the experimental mathematics needed to support this work.
The principal permanent rank characteristic sequence is a binary sequence $r_0 r_1 ldots r_n$ where $r_k = 1$ if there exists a principal square submatrix of size $k$ with nonzero permanent and $r_k = 0$ otherwise, and $r_0 = 1$ if there is a zero diagonal entry. A characterization is provided for all principal permanent rank sequences obtainable by the family of nonnegative matrices as well as the family of nonnegative symmetric matrices. Constructions for all realizable sequences are provided. Results for skew-symmetric matrices are also included.
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is $Omega(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
