Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was just thinking about this problem:

Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry?

Thanks for helping me.

share|improve this question
2  
Can you think how the determinant of the matrix depends on a specific entry? –  Mark Bennet May 17 '12 at 17:12
add comment

4 Answers

up vote 15 down vote accepted

The determinant is a linear polynomial in any given entry, so yes.

To see that $$\det\begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{n1} & \cdots & a_{nn}\end{pmatrix}$$ depends linearly on $a_{k\ell}$ for any given $k$ and $\ell$, note that $$\det\begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{n1} & \cdots & a_{nn}\end{pmatrix}=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}=\sum_{\substack{\sigma\in S_n\\ \sigma(k)=\ell}}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}+\sum_{\substack{\sigma\in S_n\\ \sigma(k)\neq \ell}}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}$$ $$=\left(\sum_{\substack{\sigma\in S_n\\ \sigma(k)=\ell}}\operatorname{sgn}(\sigma)\prod_{\substack{i=1\\i\neq k}}^n a_{i,\sigma(i)}\right)a_{k\ell} + \left(\sum_{\substack{\sigma\in S_n\\ \sigma(k)\neq \ell}}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}\right)$$ As JeffE rightly points out below, we might have that the coefficient of $a_{k\ell}$ in the above expression is 0, and that therefore varying the value of $a_{k\ell}$ won't change the determinant. I don't see any way of guaranteeing that won't happen, but we can show that, given an $\ell$, it can't happen for every $k$: if it did, then varying the entire column $$A_\ell=\begin{pmatrix} a_{1\ell} \\ \vdots \\ a_{n\ell}\end{pmatrix}$$ in any way we want doesn't change the determinant, so (for example) $$\det(A_1\mid \cdots \mid 2A_\ell\mid \cdots \mid A_n)=\det(A_1\mid \cdots \mid A_\ell\mid \cdots \mid A_n).$$ But because the determinant of $A$ is a multilinear function of the columns, $$\det(A_1\mid \cdots \mid 2A_\ell\mid \cdots \mid A_n)=2\det(A_1\mid \cdots \mid A_\ell\mid \cdots \mid A_n)$$ so $$2\det(A_1\mid \cdots \mid A_\ell\mid \cdots \mid A_n)=\det(A_1\mid \cdots \mid A_\ell\mid \cdots \mid A_n)$$ which is impossible because the assumption that $A$ is non-singular means that $$\det(A_1\mid \cdots \mid A_\ell\mid \cdots \mid A_n)\neq0.$$ Thus, given an $\ell$, there exists at least one $k$ such that varying $a_{k\ell}$ can produce a singular matrix.

share|improve this answer
    
+1 Zev beat me to it! –  Jyrki Lahtonen May 17 '12 at 17:14
    
@zev can you please explain little more? –  srijan May 17 '12 at 17:21
    
@srijan: I've added an explanation using this formula. –  Zev Chonoles May 17 '12 at 17:32
    
But what if the coefficient of $a_{k\ell}$ is zero? Equivalently, what if the function $f$ such that $\det(A) = f(a_{k\ell})$ is actually constant? –  JeffE May 17 '12 at 17:37
    
@JeffE: Excellent point - I have edited my answer with a fix, does it resolve your concern? –  Zev Chonoles May 17 '12 at 17:45
show 2 more comments

If $A$ is a nonsingular matrix with rows $r_1,r_2,\ldots,r_n$, then $\{r_2,\ldots,r_n\}$ spans an $(n-1)$-dimensional subspace $P$ of $\mathbb R^n$. At least one of the standard basis vectors $e_1,e_2,\ldots,e_n$ is not in $P$, say $e_i$. Then $\{e_i,r_2,r_3,\ldots,r_n\}$ is a basis of $\mathbb R^n$, and it follows that there is a real number $c$ such that $r_1-ce_i$ is in $P$. The matrix $A'$ with rows $(r_1-ce_i),r_2,r_3,\ldots,r_n$ is singular, and it is obtained from $A$ by subtracting $c$ from the entry in the first row and $i^\text{th}$ column.


Here's a way to rephrase this somewhat more geometrically. The subspace $P$ is a hyperplane that divides $\mathbb R^n$ into two half-spaces, and $r_1$ lies in one of these halves. The line through $r_1$ in the direction of a vector $v$ has the form $\{r_1+tv:t\in\mathbb R\}$. This line is parallel to $P$ only if $v$ is in $P$; otherwise, the line will cross $P$. Since $P$ can't be parallel to all of the coordinate directions (or else it would fill up all of $\mathbb R^n$), there must be a line of the form $\{r_1+te_i:t\in\mathbb R\}$ that crosses $P$, where $e_i$ is the standard basis vector with a $1$ in the $i^\text{th}$ position and $0$s elsewhere. This means that there exists $t_0\in \mathbb R$ such that $r_1+t_0e_i\in P$. And then, linear dependence of the vectors $r_1+t_0e_i,r_2,\ldots,r_n$ means that the matrix with those rows is singular.

share|improve this answer
add comment

You definitely can do that. One way to see it is the Sherman-Morrison-Woodbury formula

$$(\mathbf A+\mathbf u\mathbf v^\top)^{-1}=\mathbf A^{-1}-\frac1{1+\mathbf v^\top\mathbf A^{-1}\mathbf u}(\mathbf A^{-1}\mathbf u\mathbf v^\top\mathbf A^{-1})$$

and let $\mathbf u$ and $\mathbf v$ be appropriate multiples of the $k$-th column of the identity matrix $\mathbf e_k$.

In particular, letting $a_{j,k}$ be an entry of the matrix $\mathbf A$, and $c$ some constant, we have

$$(\mathbf A+(c-a_{j,k})\mathbf e_j\mathbf e_k^\top)^{-1}=\mathbf A^{-1}-(c-a_{j,k})\frac1{1+(c-a_{j,k})\mathbf e_k^\top\mathbf A^{-1}\mathbf e_j}(\mathbf A^{-1}\mathbf e_j\mathbf e_k^\top\mathbf A^{-1})$$

You have to understand what the operation $\mathbf A+(c-a_{j,k})\mathbf e_j\mathbf e_k^\top$ does; as you can see, this operation corresponds to replacing the entry $a_{j,k}$ with $c$. (Write it out yourself if you need more convincing.)

What we now want to do is to find $c$ such that the denominator in the expression given above is zero; that is,

$$1+(c-a_{j,k})\mathbf e_k^\top\mathbf A^{-1}\mathbf e_j=0$$

First, we tackle the expression $\mathbf e_k^\top\mathbf A^{-1}\mathbf e_j$. Letting $\mathbf W=\mathbf A^{-1}$, $\mathbf e_k^\top\mathbf W\mathbf e_j$ is in fact the $(k,j)$ entry of $\mathbf W$, which we will denote by $w_{k,j}$. Our equation is now

$$1+(c-a_{j,k})w_{k,j}=0$$

and we can now solve for the value of $c$ that will make $\mathbf A$ singular if it replaces $a_{j,k}$:

$$c=a_{j,k}-\frac1{w_{k,j}}$$

share|improve this answer
    
Apparently the constructive approach is unpopular. :P –  J. M. May 17 '12 at 18:00
3  
Popular with me, since it is ordinarily more informative. –  André Nicolas May 17 '12 at 18:06
    
@J.M. I was not aware of the Sherman-Morrison-Woodbury formula. But now i am studying. Sincerely thanks to you. –  srijan May 18 '12 at 1:33
add comment

Here's a fast solution. The adjugate matrix $\def\adj{\operatorname{adj}}\adj A$ satifies (more or less by definition) $$ \adj A\cdot A=\det(A)I_n, $$ and the right hand side is nonzero by the nonsingular hypothesis. Now looking at what contributes the diagonal entry $\det(A)$ at position $k,k$ on the right, one sees that of row $k$ of $\adj A$, which I will denote $(c_1~\ldots~c_n)$ and column $k$ of $A$, which I will denote $(x_1~\ldots~x_n)^t$, produce a matrix product $c_1x_1+\cdots+c_nx_n=\det(A)$. Clearly $c_ix_i\neq0$ for at least one $i$. Choose such $i$, and form a matrix $A'$ by replacing the entry $x_i$ of $A$ (which is at position $(i,k)$) by $x_i-\frac{\det(A)}{c_i}$. Row $k$ of $\adj A'$ is still $(c_1~\ldots~c_n)$ (since it does not depend on column $k$ of $A$), and the $(k,k)$ entry of $\adj A'\cdot A'$ equals $c_1x_1+\cdots+c_nx_n-c_i\frac{\det(A)}{c_i}=0$. But it is also equal to $\det(A')$, so $A'$ is singular.

This shows that not only the answer is "yes, you can make any real invertible matrix singular by changing a single entry", you can even specify in advance the column in which an entry must change. Or the row, by transposition of the argument (but not both). And it works over any field.

share|improve this answer
    
(+1) This is exactly what I had in mind when I first saw the problem. –  i707107 Apr 2 '13 at 8:27
add comment

Your Answer

 
discard

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

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