boolean matrix product

for $\text{[math]}$ and boolean matrices $\text{[math]}$ , the boolean matrix product results in a boolean matrix $\text{[math]}$ of size $\text{[math]}$ , defined by
$\text{[math]}$ for $\text{[math]}$ and $\text{[math]}$ . let the binary function $\text{[math]}$ denote this operation.
[cite:;taken from @complexity_wegener_2009 chapter 6.8 boolean matrix product]

a broken link: blk:monotone boolean function that computes $\text{[math]}$ reqires $\text{[math]}$ AND gates and $\text{[math]}$ OR gates.
[cite:;found in @computation_savage_1998 lemma 9.6.3]
[cite:;found in @complexity_wegener_2009 chapter 6.8 boolean matrix product; theorem 8.1]

the notation $\text{[math]}$ used here is equivalent to $\text{[math]}$ .

the definition can be used as an algorithm to compute $\text{[math]}$ for $\text{[math]}$ , from the entries in matrices $\text{[math]}$ and $\text{[math]}$ . we call this the standard matrix-multiplication algorithm. it uses $\text{[math]}$ ANDs and $\text{[math]}$ ORs. we now show that every monotone circuit for matrix multiplication requires at least this many ANDs and ORs.

every monotone circuit for boolean matrix multiplication $\text{[math]}$ requires at least $\text{[math]}$ OR gates.
[cite:;taken from @computation_savage_1998 chapter 9.6 lower-bound methods for monotone circuits; lemma 9.6.3]

in monotone_boolean_function.html we identified a set $\text{[math]}$ of gates called the bottleneck associated with each input variable $\text{[math]}$ . we demonstrated that each of these gates can be eliminated by setting $\text{[math]}$ and that $\text{[math]}$ has at least $\text{[math]}$ gates, where $\text{[math]}$ is the number of circuit outputs that depend essentially on $\text{[math]}$ and have at least two prime implicants. these results were shown by proving that all gates in $\text{[math]}$ are OR gates and that the $\text{[math]}$ -th of these gates' associated function contains a prime implicant of the form $\text{[math]}$ for $\text{[math]}$ . we then demonstrated that the dependence of the outputs in $\text{[math]}$ on the input $\text{[math]}$ can be eliminated by setting $\text{[math]}$ for $\text{[math]}$ , but this contradicts the definition of a semi-definite bilinear form if $\text{[math]}$ . finally, we proved that by setting $\text{[math]}$ each of the gates in $\text{[math]}$ could be eliminated. for this lemma, we need only strengthen the lower bound on $\text{[math]}$ for matrix multiplication.
consider a minimal circuit. the proof is by induction on $\text{[math]}$ , with the base case being $\text{[math]}$ . in the base case $\text{[math]}$ for $\text{[math]}$ and $\text{[math]}$ and no ORs are needed. as inductive hypothesis we assume that $\text{[math]}$ requires at least $\text{[math]}$ OR gates. we show that setting any column of $\text{[math]}$ in $\text{[math]}$ to 0 eliminates $\text{[math]}$ OR gates and reduces the problem to an instance of $\text{[math]}$ . it follows that $\text{[math]}$ requires $\text{[math]}$ OR gates.
when $\text{[math]}$ , each output function $\text{[math]}$ has at least two prime implicants. we apply the bottleneck argument to this case. consider the bottleneck $\text{[math]}$ associated with input variable $\text{[math]}$ . we show that $\text{[math]}$ , from which it follows that at least $\text{[math]}$ OR gates can be eliminated by setting $\text{[math]}$ . this reduces the problem to another set of bilinear forms. repeating this for $\text{[math]}$ , we eliminate $\text{[math]}$ OR gates, one column of $\text{[math]}$ , and one row of $\text{[math]}$ . let $\text{[math]}$ be the outputs that depend on $\text{[math]}$ .
to show that $\text{[math]}$ , let the gate of $\text{[math]}$ compute $\text{[math]}$ for $\text{[math]}$ . here $\text{[math]}$ and $\text{[math]}$ for some $\text{[math]}$ and $\text{[math]}$ . if we set all entries in $\text{[math]}$ to 1, we eliminate all dependence of outputs in $\text{[math]}$ on $\text{[math]}$ . however, since $\text{[math]}$ , the set $\text{[math]}$ must contain at least one variable used in $\text{[math]}$ for each $\text{[math]}$ . thus, $\text{[math]}$ .

every monotone circuit for Boolean matrix multiplication $\text{[math]}$ requires at least $\text{[math]}$ AND gates.

consider a minimal circuit. the proof is by induction on $\text{[math]}$ , the base case being $\text{[math]}$ . in the base case $\text{[math]}$ for $\text{[math]}$ and $\text{[math]}$ and $\text{[math]}$ ANDs are needed, since $\text{[math]}$ results must be computed, each requiring one AND, and all functions are different. as inductive hypothesis we assume that $\text{[math]}$ requires at least $\text{[math]}$ AND gates. we show that setting any column of $\text{[math]}$ in $\text{[math]}$ to 1 and the corresponding row of $\text{[math]}$ to 0 eliminates $\text{[math]}$ AND gates and reduces the problem to an instance of $\text{[math]}$ . it follows that $\text{[math]}$ requires $\text{[math]}$ AND gates.
for arbitrary $\text{[math]}$ let $\text{[math]}$ be a gate closest to inputs computing a function $\text{[math]}$ such that $\text{[math]}$ contains $\text{[math]}$ . since the gate associated with $\text{[math]}$ has $\text{[math]}$ as a prime implicant, there is such a gate $\text{[math]}$ . furthermore, $\text{[math]}$ must be an $\text{[math]}$ gate because $\text{[math]}$ gates cannot generate new prime implicants. let $\text{[math]}$ and $\text{[math]}$ be gates generating inputs for $\text{[math]}$ . let them compute functions $\text{[math]}$ and $\text{[math]}$ . it follows from the definition of $\text{[math]}$ that $\text{[math]}$ and $\text{[math]}$ or vice versa. let the former hold. if $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ can be eliminated. we now show that $\text{[math]}$ for $\text{[math]}$ . suppose not. since $\text{[math]}$ or $\text{[math]}$ , there are at least three distinct variables among $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . therefore either $\text{[math]}$ or $\text{[math]}$ has at least two of these variables as prime implicants. by boolean_formula.html this circuit is not minimal, a contradiction.

[cite:;taken from @computation_savage_1998 chapter 9 circuit complexity]