0

I am reading: Boolean Matrix Theory by K.H. Kim. On page 37 the definition for Schein rank is given.

Def 1.4.1: For vectors $v,w$ the symbol $c(v,w)$ will denote the matrix $(v_i w_j)$. Such matrices are called cross-vectors.

Def 1.4.2: The Schein rank of a matrix $A$ is the least number of cross-vectors whose sum is $A$.

Example 1.4.1 $A = \left( \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ \end{array} \right)$

The text states the Schein rank of $A$ is $3$.

Why is the Schein rank equal to $3$? What $3 $ cross-vectors sum to $A$.

Sam Hoffman
  • 535
geoffrey
  • 48
  • I don't think this is true, since the actual rank of A is four. If I am not crazy right now then the rank is always less or equal to the schein rank. – PhoemueX Jan 17 '23 at 17:52
  • I understand why the row rank and column rank of A are both equal to 4. A theorem in the text says that the Schein rank is at most the minimum of the row rank and column rank. – geoffrey Jan 17 '23 at 17:56

1 Answers1

2

A cross-vector is a Boolean matrix which is a result of product of two Boolean vectors.

Example: for $v = (1,1,0,0), w = (0,1,1,0)$ we have $$ c(v,w) = \left( \begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}\right) \circ \left( \begin{matrix} 0 & 1 & 1 & 0 \end{matrix} \right) = \left( \begin{matrix} 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} \right). $$

The matrix has Schein rank 3 because it is $$ A = \left( \begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} \right) \vee \left( \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} \right) \vee \left( \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{matrix} \right). $$

Jan Konecny
  • 36