Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Trying to build a reduction from the maximum coverage problem to my research problem, I'm facing this difficulty :

Let $X$ be a $n \times m$ binary matrix (with $m > n$), can we define a square matrix $M = \begin{bmatrix} A & X\\ X^\top & B \end{bmatrix}$ such that $\det M$ is related to the number of non zero columns of $X$ ?

All my attempts failed, but perhaps I was looking in a wrong direction...

share|cite|improve this question
How should that work? Can you give an example? – draks ... Sep 27 '12 at 9:06
The matrices $A$ and $B$ could be anything, for example an empty matrix $A$ and identity for $B$. And by a "relation" between $det M$ and $nzc(X)$ the number of non zero columns of $X$, I meant $det M = f(nzc(X))$ with any monotonic function $f$. – Emile Sep 27 '12 at 9:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.