Showing we can remove one column and still the array satisfying the property with induction or with graph theory 
A $n * n$ array of numbers is constructed so that no two rows are same . Show that we can delete a column such that even then no two rows are same .


*

*My progress:.                         I tried induction with base case $n=1$ which is true . For case $n=2$ we have atleast one column to be having different numbers otherwise if both columns had same number we would be getting same rows which is not possible according to question . Now supposing it to be true for some $k * k$ , i am not able to prove it for ${k+1} * {k+1}$. Since i dont know what cases be need to be made for this .


Is there a proper way with induction to solve this ?


*

*Note: A Graph Theory based solution also works because it was a problem given in a Graph theory video .           Is showing the contradictory much easier to prove false ?

 A: Draw a graph whose vertices are the rows. For each column, if possible, pick one pair of rows that would become the same if that column were deleted, and put an edge between them.  As a result, going from a vertex to an adjacent vertex in this graph always changes the row in a single position, and different edges change different positions.
There cannot be a cycle in this graph. That would mean we started at a row and changed it in several completely different positions to return to the same row.
Since the graph is acyclic and has $n$ vertices, it must have at most $n-1$ edges, which means there was at least one column for which we did not draw an edge. We can delete any such column.
A: Call an $m{\times}n$ matrix $A$ row-distinct if no two rows are equal.

For convenience of notation, if $A$ is an $m{\times}n$ matrix and $J$ is a nonempty subset of $\{1,...,n\}$, let $A_J$ denote the $m{\times}|J|$ matrix obtained from $A$ by removing all columns except those whose indices are in $J$.

It's immediate that if $A$ is an $m{\times}n$ matrix and $J'$ is a nonempty subset of $\{1,...,n\}$ such that $A_{J'}$ is row-distinct, then $A_J$ is also row-distinct for any
set $J$ with $J'\subseteq J\subseteq\{1,...,n\}$.

The desired result is the case $m=n$ of the following more general claim . . .

Claim:$\;$If an $m{\times}n$ matrix $A$ with $2\le m\le n$ is row-distinct, there exists $J\subset\{1,...,n\}$ with $|J|=m-1$ such that the $m{\times}(m-1)$ matrix $A_J$ is also row-distinct.

Proof:

For integers $m,n$ with $2\le m\le n$, let $Q(m,n)$ denote the above claim, and for each integer $m\ge 2$, let $P(m)$ denote the claim that $Q(m,n)$ holds for all integers $n\ge m$.

Our goal is to prove that $P(m)$ holds for all integers $m\ge 2$.

Proceed by induction on $m$ . . .

First consider the base case $P(2)$.

For an integer $n\ge 2$, let $A$ be a $2{\times}n$ row-distinct matrix.

Since $A$ is row-distinct, there is at least one column of $A$ with two unequal entries, hence if we choose one such column and remove all other columns, the resulting $2{\times}1$ matrix is such that no two rows are equal.

Thus $P(2)$ is verified.

Next let $m$ be the least integer with $m > 2$ such that $P(m)$ has not yet been established.

For that value of $m$, to complete the induction, our goal is to prove $P(m)$.

Fix an integer $n\ge m$, and let $A$ be an $m{\times}n$ row-distinct matrix.

Since $A$ is row-distinct, some column of $A$ must be such that not all entries in that column are equal.

Without loss of generality, permuting the columns of $A$ as necessary, assume 
column $n$ of $A$ is such that not all entries in that column are equal.

Consider two cases . . .

Case $(1)$:$\;$Some entry in column $n$ of $A$ occurs exactly once in column $n$.

Suppose the entry $x$ occurs exactly once in column $n$.

Without loss of generality, permuting the rows as necessary, assume row $1$ is the row whose column $n$ entry is equal to $x$.

Let $B$ be the $(m-1){\times}n$ matrix obtained from $A$ by removing row $1$.

Since $A$ is row-distinct, so is $B$.

Applying the inductive hypothesis to $B$, there exists a set $J'\subset\{1,...,n\}$ with $|J'|=m-2$ such that $B_{J'}$ is row-distinct.

From $|J'|=m-2$, we get $|J'\cup\{n\}|\le m-1$, hence there exists a set $J$ with $J'\cup\{n\}\subseteq J\subset\{1,...,n\}$ such that $|J|=m-1$.

Since $B_{J'}$ is row-distinct, so is $B_J$.

Then since $n\in J$ and none of the entries in column $n$ of $B$ are equal to $x$, it follows that $A_J$ is row-distinct.

Hence for case $(1)$, the claim $P(m)$ holds.

Case $(2)$:$\;$Column $n$ of $A$ has at least two distinct entries, and each entry in column $n$ occurs more than once in column $n$.

Suppose the entry $x$ occurs exactly $m_1$ times in column $n$ of $A$, and let $m_2=m-m_1$.

Then $m_1,m_2\ge 2$ and $m_1+m_2=m$.

Without loss of generality, permuting the rows as necessary, assume rows $1$ through $m_1$ of $A$ are the rows whose column $n$ entry is equal to $x$.

Let $B_1$ be the $m_1{\times}n$ matrix obtained from $A$ by removing all rows except rows $1$ through $m_1$, and let $B_2$ be the $m_2{\times}n$ matrix obtained from $A$ by removing rows $1$ through $m_1$.

Since $A$ is row-distinct, so are $B_1$ and $B_2$.

Applying the inductive hypothesis to each of $B_1,B_2$

*

*$(B_1)_{J_1}$ is row-distinct for some set $J_1\subset\{1,...,n\}$ with $|J_1|=m_1-1$.$\\[4pt]$

*$(B_2)_{J_2}$ is row-distinct for some set $J_2\subset\{1,...,n\}$ with $|J_2|=m_2-1$.

From $|J_1|=m_1-1$ and $|J_2|=m_2-1$, we get
$$
|J_1\cup J_2\cup\{n\}|\le (m_1-1)+(m_2-1)+1=m-1
$$
hence there exists a set $J$ with
$J_1\cup J_2\cup\{n\}\subseteq J\subset\{1,...,n\}$
such that $|J|=m-1$.

Since $(B_1)_{J_1}$ and $(B_2)_{J_2}$ are row-distinct, so are $(B_1)_J$ and $(B_2)_J$.

Then since $n\in J$ and none of the entries in column $n$ of $B_2$ are equal to $x$, it follows that $A_J$ is row-distinct.

Hence for case $(2)$, the claim $P(m)$ holds.

Thus in both cases, the claim $P(m)$ holds, which completes the induction.

This completes the proof.
