Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$ $$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$ hold ($per$ refers to permanent).
I. What is the behavior of each of the following in the regime $z\in[0,1]$?
- $\det(zA_1+(1-z)A_2)$ and $per(zA_1+(1-z)A_2)$
- $\det(zB_1+(1-z)B_2)$ and $per(zB_1+(1-z)B_2)$
At the end points $z\in\{0,1\}$ the values are in $\{0,1\}$.
II. Given two matrices $M_1,M_2$ where $M_i=A_i$ or $B_i$ at every $i\in\{1,2\}$ can we decide which is the case in time polynomial in $n$ without computing any determinants or permanents?
\det$\endgroup$