0
$\begingroup$

By rank I imply rank over reals ($\mathbb R$).

I consider two $n\times n$ matrices $A,B$ having entries in $0/1$.

The product below follows usual matrix product rules except $xy$ is $AND(x,y)$ and $x+y$ is $OR(x,y)$.

Assume real rank of $AB$ is $n$ and assume $det(AB)=per(AB)=1$.

  1. Would it follow $per(A)=per(B)=1$?

$1$. implies $rank(A)=rank(B)=n$.

Assume real rank of $AB$ is $<n$ and assume $det(AB)=per(AB)=0$.

  1. Would it follow $per(A)per(B)=0$ and would it imply $rank(A)+rank(B)<2n$.
  1. How about the status of 1. and 2. if product remains Boolean product but rank is determined in $\mathbb F_2$?
$\endgroup$
3
  • 1
    $\begingroup$ 1) $\mathrm{per}(AB)=1$ (in reals) is a very strong condition for a matrix valued in non-negative integers: it means that among all $n!$ terms, all but 0 are 0, and the remaining one is $1$ (hence corresponding to $n$ entries equal to $1$). $\endgroup$
    – YCor
    Jun 16, 2021 at 9:34
  • 1
    $\begingroup$ A simple program could easily check the $2^8$ and $2^{18}$ possible pairs of $2\times 2$ and $3\times 3$ matrices. (Using invariance under left-multiplying $A$ by a permutation matrix and similarly $B$ on the right, and simultaneously multiplying $A$ on the right by a permutation matrix $P$ and $B$ on the left by $P^{-1}$, would decrease the number of computations in case one would want to check $4\times 4$. $\endgroup$
    – YCor
    Jun 16, 2021 at 9:41
  • $\begingroup$ The product for 2x2 implies wlog af+bh=0 (or per(AB)>1) in ((a,b),(c,d)) x((e,f),(g,h)) while ae+bg=cf+dh=1. Hence a=0 implies h=0 and b=g=c=f=1. It verifies 1. on per(A)=per(B)=1. $\endgroup$
    – User2021
    Jun 16, 2021 at 9:54

1 Answer 1

0
$\begingroup$

For $n = 3$, 1) is false: let $A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ and $B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$.

Some obvious modifications to the code below also show that the first question in 2) is false: let $A$ be as before and $B = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$.

Similarly, the second question in 2) is false: let $A'' = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ and $B'' = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$.

Question 3) takes longer to test since the GF(2) arithmetic is slower(!) in MATLAB. The analogue of 1) holds for $n = 3$. The analogue of the second question in 2) also holds for $n = 3$, but the analogue of the first question in 2) does not: here a counterexample is furnished by $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ and $\begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix}$.

The MATLAB code I used for 1) is below. It requires the communications toolbox and a third-party function for the permanent as indicated in a code comment.

n = 3;
if n < 2, error('n < 2'); end
if n > 4, error('n > 4'); end
for j = 0:((2^(n^2))-1)
    bits_j = bitget(j,1:n^2,'uint32');
    A_R = reshape(bits_j,[n,n]);    % real
    rankA = rank(A_R);
    A = gf(A_R);    % GF(2) vs real
    for k = 0:((2^(n^2))-1)
        bits_k = bitget(k,1:n^2,'uint32');
        B_R = reshape(bits_k,[n,n]);    % real
        rankB = rank(B_R);
        B = gf(B_R);    % GF(2) vs real
        AB = double(getfield(A*B,'x')); % real vs GF(2)
        r = rank(AB);
        if r == n
            if det(AB) == 1
                % Permanent using
                % https://www.mathworks.com/matlabcentral/fileexchange/22194-matrix-permanent
                per = permanent(AB);
                if per == 1
                    perA = permanent(A_R);
                    perB = permanent(B_R);
                    if any([perA,perB]~=[1,1])
                        disp(A_R);
                        disp(B_R);
                        error('violation');
                    end
                end
            end
        end
    end
end
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.