8
$\begingroup$

What is the minimum value of $k$ such that every non-singular $n\times n$ real matrices can be made singular by switching EXACTLY $k$ entries with ZERO ?

$\endgroup$
4
$\begingroup$

You can always make an $n \times n$ matrix singular by making $n$ entries ( all in one row or one column) zero. For a matrix $(a_{ij})$ whose entries are algebraically independent, it is impossible to do with fewer than $n$. You can prove (e.g. using Hall's marriage theorem) that if you make fewer than $n$ elements zero there will still be a permutation $\pi$ of $[1,\ldots,n]$ such that all $a_{i,\pi(i)}$ are unaffected, so the corresponding term in the determinant will still be there and can't be cancelled by the other terms.

EDIT: This is, of course, over a field that has $n^2$ algebraically independent elements. You can do it over any infinite field, with a bit more work, by constructing inductively a sequence $c_j$ of nonzero elements such that for each $n$, all terms of the following form are distinct and nonzero: $\sum_{i=1}^k \prod_{j \in S_i} c_j$ where $S_1, \ldots, S_k$ are distinct subsets of $\{1, \ldots, n\}$, $1 \le k \le 2^n$. On the other hand, it doesn't work over finite fields. Thus over $GF(2)$ you can always make a nonsingular matrix singular by changing one element to $0$.

$\endgroup$

Your Answer

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

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