A bandstructure-invariant deflation for real symmetric matrices

By means of an eigenvector and eigenvalue of a real symmetric matrix A, a unitary matrix U is constructed such that U¹AU deflates A and, moreover, the transformation preserves the bandstructure.     

Anomalies of weakened decoherence criteria for quantum histories

The theory of decoherent histories is checked for the requirement of statistical independence of subsystems. Strikingly, this is satisfied only when the decoherence functional is diagonal in both its real and imaginary parts. Although the weakened condition of consistency (or weak decoherence), allowing a nondiagonal imaginary part, is sufficient for the assignment of probabilities, it may easily violate the statistical independence of subsystems. Therefore, weakened consistency conditions and various related generalizations of the concept of decoherent histories appear to be ruled out. The same conclusion is obtained independently, by claiming a plausible dynamical robustness of decoherent histories.     

Standard monomials for <Emphasis Type="Italic">q</Emphasis>-uniform families and a conjecture of Babai and Frankl

Let n, k, α be integers, n, α>0, p be a prime and q=p ^α. Consider the complete q-uniform family

$\mathcal{F}\left( {k,q} \right) = \left\{ {K \subseteq \left[ n \right]:\left| K \right| \equiv k(mod q)} \right\}$

We study certain inclusion matrices attached to F(k,q) over the field\(\mathbb{F}_p \). We show that if l≤q?1 and 2l≤n then

$rank_{\mathbb{F}_p } I(\mathcal{F}(k,q),\left( {\begin{array}{*{20}c} {\left[ n \right]} \\ { \leqslant \ell } \\ \end{array} } \right)) \leqslant \left( {\begin{array}{*{20}c} n \\ \ell \\ \end{array} } \right)$

This extends a theorem of Frankl [7] obtained for the case α=1. In the proof we use arguments involving Gröbner bases, standard monomials and reduction. As an application, we solve a problem of Babai and Frankl related to the size of some L-intersecting families modulo q.     

On the number of zero-patterns of a sequence of polynomials

Let be a sequence of polynomials of degree in variables over a field . The zero-pattern of at is the set of those ( ) for which . Let denote the number of zero-patterns of as ranges over . We prove that for and

for . For , these bounds are optimal within a factor of . The bound () improves the bound proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz's but slightly weaker than () follow from results of J. Milnor (1964), H.E.  Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary ``linear algebra bound'.

Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the ``branching program' model in the theory of computing, asserts that over any field , most graphs with vertices have projective dimension (the implied constant is absolute). This result was previously known over the reals (Pudlák-Rödl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.