0
$\begingroup$

This is a more focused version of a question (unresolved) about finding the inverse of a system of Boolean equations. For a vector space over the reals, the inverse function theorem says that the inverse of the Jacobian matrix gives us the Jacobian of the inverse. Can we do likewise for a module endomorphism $\mathbf{f} : \mathbb{B}^n \to \mathbb{B}^n$?

In the Boolean differential calculus, the derivative for a scalar is defined as $$ \frac{df}{dx} = f\rvert_{x=0} + f\rvert_{x=1} $$ where $(+)$ indicates exclusive OR. Up to chain and product rules, this works like "normal" differentiation. There is a short paper [1] (h/t this post) assessing the criteria for a Boolean matrix to be invertible, the main one being orthogonality; do its results extend to a matrix of Boolean polynomials, namely the Jacobian $J_{\mathbf{f}}$ using Boolean partial derivatives?

Conjecture (false): If $J_{\mathbf{f}} \cdot J_{\mathbf{f}}^{T} = I$, then $\mathbf{f}^{-1}$ exists, and I can find it by iterated antidifferentiation on the rows of $J_{\mathbf{f}}^{T}$.

(False because a Boolean function is always polylinear, and $ \forall x\ \frac{d^2 f}{dx^2}=0$. This can easily turn out not the case for $J_{\mathbf{f}}^{T}$.)

What next?


[1] Rutherford, D. E. (1963). Inverses of Boolean matrices. Proceedings of the Glasgow Mathematical Association, 6(1), 49–53. doi: 10.1017/s2040618500034705

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.