Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSign patterns with minimum rank 3 and point-line configurations
144
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A emph{sign pattern (matrix)} is a matrix whose entries are from the set ${+, -, 0}$. The emph{minimum rank} (respectively, emph{rational minimum rank}) of a sign pattern matrix $cal A$ is the minimum of the ranks of the real (respectively, rational) matrices whose entries have signs equal to the corresponding entries of $cal A$. A sign pattern $cal A$ is said to be emph{condensed} if $cal A$ has no zero row or column and no two rows or columns are identical or negatives of each other. In this paper, a new direct connection between condensed $m times n $ sign patterns with minimum rank $r$ and $m$ point--$n$ hyperplane configurations in ${mathbb R}^{r-1}$ is established. In particular, condensed sign patterns with minimum rank 3 are closed related to point--line configurations on the plane. It is proved that for any sign pattern $cal A$ with minimum rank $rgeq 3$, if the number of zero entries on each column of $cal A$ is at most $r-1$, then the rational minimum rank of $cal A$ is also $r$. Furthermore, we construct the smallest known sign pattern whose minimum rank is 3 but whose rational minimum rank is greater than 3.
rate research
Read More
A {it sign pattern matrix} is a matrix whose entries are from the set ${+,-, 0}$. The minimum rank of a sign pattern matrix $A$ is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of $A$. It is shown in this paper that for any $m times n$ sign pattern $A$ with minimum rank $n-2$, rational realization of the minimum rank is possible. This is done using a new approach involving sign vectors and duality. It is shown that for each integer $ngeq 9$, there exists a nonnegative integer $m$ such that there exists an $ntimes m$ sign pattern matrix with minimum rank $n-3$ for which rational realization is not possible. A characterization of $mtimes n$ sign patterns $A$ with minimum rank $n-1$ is given (which solves an open problem in Brualdi et al. cite{Bru10}), along with a more general description of sign patterns with minimum rank $r$, in terms of sign vectors of certain subspaces. A number of results on the maximum and minimum numbers of sign vectors of $k$-dimensional subspaces of $mathbb R^n$ are obtained. In particular, it is shown that the maximum number of sign vectors of $2$-dimensional subspaces of $mathbb R^n$ is $4n+1$. Several related open problems are stated along the way.
A sign pattern matrix is a matrix whose entries are from the set ${+,-,0}$. If $A$ is an $mtimes n$ sign pattern matrix, the qualitative class of $A$, denoted $Q(A)$, is the set of all real $mtimes n$ matrices $B=[b_{i,j}]$ with $b_{i,j}$ positive (respectively, negative, zero) if $a_{i,j}$ is + (respectively, $-$, 0). The minimum rank of a sign pattern matrix $A$, denoted $mr(A)$, is the minimum of the ranks of the real matrices in $Q(A)$. Determination of the minimum rank of a sign pattern matrix is a longstanding open problem. For the case that the sign pattern matrix has a 1-separation, we present a formula to compute the minimum rank of a sign pattern matrix using the minimum ranks of certain generalized sign pattern matrices associated with the 1-separation.
Our main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field.
In Martin Gardners October, 1976 Mathematical Games column in Scientific American, he posed the following problem: What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal? We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.
The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity / minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z_+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
