Return to Answer

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose adjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1+x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable. One can get rid of the constants $1$ in the matrix as follows: we include in $M$ the identity matrix as yet another block, and then we replace $1$ with a new variable $x_0$ everywhere (i.e., in the $1$ entries as well as in the entries of the form $1+x_k$). Any assignment making the new matrix invertible must have $x_0=1$, and then it works as before. The new matrix has only entries of the form $0$, $x_k$, $x_0+x_k$.

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose biadjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1+x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable. One can get rid of the constants $1$ in the matrix as follows: we include in $M$ the identity matrix as yet another block, and then we replace $1$ with a new variable $x_0$ everywhere (i.e., in the $1$ entries as well as in the entries of the form $1+x_k$). Any assignment making the new matrix invertible must have $x_0=1$, and then it works as before. The new matrix has only entries of the form $0$, $x_k$, $x_0+x_k$.

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose adjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1-x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable.

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose adjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1+x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable. One can get rid of the constants $1$ in the matrix as follows: we include in $M$ the identity matrix as yet another block, and then we replace $1$ with a new variable $x_0$ everywhere (i.e., in the $1$ entries as well as in the entries of the form $1+x_k$). Any assignment making the new matrix invertible must have $x_0=1$, and then it works as before. The new matrix has only entries of the form $0$, $x_k$, $x_0+x_k$.

I assume that by non-degenerate you mean non-singular, and I assume that $k$ is a finite field.

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose adjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose adjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1-x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable.