1
$\begingroup$

I'm studying discrete mathematics and this week's homework (which is supposed to be about induction) included this question:

Let $M$ be a $m \times n$ - ordered matrix whose cells are only zeros or ones and which contains at least one cell whose value is $1$.

A cell whose value is $1$ will be called "good" if one or more of the following criteria are met:

  • The cell is in the first row of $M$
  • The cell is in the first column of $M$
  • The cell above it and the cell to the left of it are both $0$ - that is, for the $(i,j)$ cell to be "good", the $(i-1,j)$ and $(i,j-1)$ cells must both be $0$ (assuming $i,j \neq 1$) .

Prove that $M$ contains at least one "good" cell.

Hint: prove inductively that for every $s \geq 2 \in \mathbb{N}$ , if $m+n=s$ then $M$ has a good cell.

~

I thought about it for a while and realized that the first $1$ in the first non-zero row of $M$ will be a "good" cell regardless of the matrix's dimensions. Now, I know that stating this fact doesn't constitute an acceptable proof; my trouble is finding a way to prove it inductively.

Using the hint provided in the question I surmised that the base case for an inductive proof of this argument is a $1 \times 1$ matrix whose only cell contains $1$. The inductive argument would then be:

If a matrix $M_{m \times n}$ where $m+n = k-1 \geq 2$ contains a "good" cell, then a matrix $M'_{p \times q}$ where $p+q = k > 2$ also contains a good cell.

I started the proof itself like so:

Let $k > 2 \in \mathbb{N^+}$ and let $M_{m \times n}$ be a matrix as described in the problem where $m+n=k-1\geq2$ . We'll assume this matrix contains a "good" cell. We'll add a row or column to $M$ arbitrarily and prove that the resulting matrix $M'_{p \times q}$ where $p+q = k > 2$ also has a "good" cell in it.

Let $i,j \in \mathbb{N^+}$ so that the $(i,j)$ cell in $M$ is "good". Upon adding a row or column to the matrix $M$ , one of two possibilities may be true:

1) The $i,j$ cell in $M'$ is still "good", which means the row or column that was added to $M$ was added after the $i$ row or after the $j$ column, respectively.

2) The $i,j$ cell in $M'$ is not good, which means that either the cell above it or to the left of it is now $1$.

~

The second possibility is where things start getting messy (for me, at least) because since the row or column was added to $M$ arbitrarily there really is no way to use the placement of the "good" cell in $M$ to locate the "good" cell in $M'$...

Either I'm approaching this problem the wrong way or there's something here I'm missing, but either way I'm pretty stumped as to how to proceed from there. Does anyone have any ideas?

$\endgroup$
  • $\begingroup$ You could just fix $n$, the number of columns and induct on $m$, the number of rows. That way your first observation, "I thought about it for a while and realized that the first 11 in the first non-zero row of MM will be a "good" cell regardless of the matrix's dimensions.", can be modified easily into an argument for completing the induction. $\endgroup$ – VENKITESH Dec 23 '17 at 15:24
  • $\begingroup$ Interesting - could you elaborate? It seems to me that this approach precludes a need for two inductive proofs: one for the rows and one for the columns. Assuming I go this route, how exactly would one adapt my observation into a sound argument? $\endgroup$ – Or Bairey-Sehayek Dec 23 '17 at 22:29
  • $\begingroup$ Well, on thinking of it again, your first observation is infact a full proof with just a technical addition. You don't even need induction on $m$ with fixed $n$. I have posted the answer. $\endgroup$ – VENKITESH Dec 24 '17 at 7:14
1
$\begingroup$

The matrix $M$ is a function $M:\{1,\ldots,m\}\times\{1,\ldots,n\}\to\{0,1\}$. Define an order $<$ on $\{1,\ldots,m\}\times\{1,\ldots,n\}$ as

$$(i,j)<(k,l)\quad\text{if either }(i<k)\text{ or }(i=k\text{ and }j<l)$$

This gives a total order on $\{1,\ldots,m\}\times\{1,\ldots,n\}$ and the elements can be listed as $$(1,1)<\cdots<(1,n)<(2,1)<\cdots<(2,n)<\cdots<(m,1)<\cdots<(m,n)$$

Now given the matrix $M$, if every $M(i,j)=0$, then $M=0$. So suppose $M\ne0$. Let $D=\{(i,j):M(i,j)=1\}$. Then since $M\ne0$, we have $D\ne\emptyset$. Let $(s,t)$ be the smallest element in $D$ with respect to the given order $<$. Such an element exists and is unique since $<$ is a total order on a finite set $\{1,\ldots,m\}\times\{1,\ldots,n\}$.

If the elements $(s-1,t),(s,t-1)$ exist, that is, if $s>1$ or $t>1$ (respectively), then clearly $(s-1,t)<(s,t)$ and $(s,t-1)<(s,t)$. So by the 'smallest element' choice, $(s-1,t),(s,t-1)\not\in D$. So $M(s-1,t)=M(s,t-1)=0$ and hence $(s,t)$ is good.

Alternate Solution using Induction:

We fix $n$, the number of columns and induct on $m$, the number of rows. The result is obvious for a nonzero $1\times n$ matrix (which is a vector), since the first nonzero cell will be a good cell. Suppose the result holds true for any nonzero $m\times n$ matrix.

Now let $M$ be an $(m+1)\times n$ matrix such that $M\ne0$. Let $M'$ be the matrix obtained from $M$ by deleting the $(m+1)$-th row and let $R$ be the $(m+1)$-th row of $M$. So $M'$ is an $m\times n$ matrix. If $M'=0$, then $R\ne0$ since $M\ne0$ and hence by base case, $R$ has a good cell, say $(s,t)$. (Note that $R$ can be naturally identified with a vector.) Since $M'=0$, it follows that $(s,t)$ is also a good cell of $M$.

Now suppose $M'\ne0$. Then by induction hypothesis, $M'$ has a good cell, say $(s,t)$. Then again $(s,t)$ is a good cell of $M$.

Hence by induction, $M$ has a good cell.

$\endgroup$
  • $\begingroup$ This is an excellent solution but I'm fairly certain that my professor won't accept any answer that doesn't involve induction :( It's annoying but it is what it is... Do you think there's any way to do it inductively without having to induct on the rows and columns separately? There's a quiz about this later this week and we're supposed to be able to handwrite an answer to this question in fifteen minutes or less. $\endgroup$ – Or Bairey-Sehayek Dec 25 '17 at 15:05
  • $\begingroup$ I have added an induction version, along the lines of what I mentioned before, in my original answer post. Check! $\endgroup$ – VENKITESH Dec 26 '17 at 5:01

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.