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 @math be a set of points in @math such that for every @math there exists at least @math values of @math such that the line through @math contains a third point in the set. We show that the dimension of @math is at most @math . 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).
Another place where the support of a matrix is connected to its rank is in graph theory where we are interested in minimizing the rank of a (square, symmetric) real matrix which has the same support as the adjacency matrix of a given graph. This line of work goes back for over fifty years and has many applications in graph theory. See @cite_11 for a recent survey on this topic.
@cite_11
1969872431 2951997246 2074032690 1641749581
Abstract We consider the problem of the presence of short cycles in the graphs of nonzero elements of matrices which have sublinear rank and nonzero entries on the main diagonal, and analyze the connection between these properties and the rigidity of matrices. In particular, we exhibit a family of matrices which shows that sublinear rank does not imply the existence of triangles. This family can also be used to give a constructive bound of the order of k 3 2 on the Ramsey number R(3,k) , which matches the best-known bound. On the other hand, we show that sublinear rank implies the existence of 4-cycles. Finally, we prove some partial results towards establishing lower bounds on matrix rigidity and consequently on the size of logarithmic depth arithmetic circuits for computing certain explicit linear transformations. We introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then omega = 2. This connection between the s-rank exponent and the ordinary exponent enables us to significantly generalize the group-theoretic approach of Cohn and Umans, from group algebras to general algebras. Embedding matrix multiplication into general algebra multiplication yields bounds on s-rank (not ordinary rank) and, prior to this paper, that had been a barrier to working with general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. Coherent configurations are combinatorial objects that generalize groups and group actions; adjacency algebras are the analogue of group algebras and retain many of their important features. As with groups, coherent configurations support matrix multiplication when a natural combinatorial condition is satisfied, involving triangles of points in their underlying geometry. Finally, we prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on omega using commutative coherent configurations and suggests that commutative coherent configurations may be sufficient to prove omega = 2. Altogether, our results show that bounds on omega can be established by embedding large matrix multiplication instances into small commutative coherent configurations, while avoiding the representation-theoretic complications that were present in the group-theoretic approach. We consider the set G consisting of graphs of fixed order and weighted edges. The vertex set of graphs in G will correspond to point masses and the weight for an edge between two vertices is a functional of the distance between them. We pose the problem of finding the best vertex positional configuration in the presence of an additional proximity constraint, in the sense that, the second smallest eigenvalue of the corresponding graph Laplacian is maximized. In many recent applications of algebraic graph theory in systems and control, the second smallest eigenvalue of Laplacian has emerged as a critical parameter that influences the stability and robustness properties of dynamic systems that operate over an information network. Our motivation in the present work is to "assign" this Laplacian eigenvalue when relative positions of various elements dictate the interconnection of the underlying weighted graph. In this venue, one would then be able to "synthesize" information graphs that have desirable system theoretic properties. This paper proposes a novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set. A graph transaction is represented by an adjacency matrix, and the frequent patterns appearing in the matrices are mined through the extended algorithm of the basket analysis. Its performance has been evaluated for the artificial simulation data and the carcinogenesis data of Oxford University and NTP. Its high efficiency has been confirmed for the size of a real-world problem.