A rank of the matrix is probably the most important concept you learn in Matrix Algebra. There are two ways to look at the rank of a matrix. One from a theoretical setting and the other from a applied setting.
From a theoretical setting, if we say that a linear operator has a rank $p$, it means that the range of the linear operator is a $p$ dimensional space.
From a matrix algebra point of view, column rank denotes the number of independent columns of a matrix while row rank denotes the number of independent rows of a matrix. An interesting, and I think a non-obvious (though the proof is not hard) fact is the row rank is same as column rank. When we say a matrix $A \in \mathbb{R}^{n \times n}$ has rank $p$, what it means is that if we take all vectors $x \in \mathbb{R}^{n \times 1}$, then $Ax$ spans a $p$ dimensional sub-space. Let us see this in a 2D setting. For instance, if
$A = \left( \begin{array}{cc}
1 & 2 \\
2 & 4 \end{array} \right) \in \mathbb{R}^{2 \times 2}$ and let $x = \left( \begin{array}{c}
x_1 \\
x_2 \end{array} \right) \in \mathbb{R}^{2 \times 1}$, then $\left( \begin{array}{c}
y_1 \\
y_2 \end{array} \right) = y = Ax = \left( \begin{array}{c}
x_1 + 2x_2 \\
2x_1 + 4x_2 \end{array} \right)$.
The rank of matrix $A$ is $1$ and we find that $y_2 = 2y_1$ which is nothing but a line passing through the origin in the plane.
What has happened is the points $(x_1,x_2)$ on the $x_1 - x_2$ plane have all been mapped on to a line $y_2 = 2y_1$. Looking closely, the points in the $x_1 - x_2$ plane along the line $x_1 + 2x_2 = c = \text{const}$, have all been mapped onto a single point $(c,2c)$ in the $y_1 - y_2$ plane. So the single point $(c,2c)$ on the $y_1 - y_2$ plane represents a straight line $x_1 + 2x_2 = c$ in the $x_1 - x_2$ plane.
This is the reason why you cannot solve a linear system when it is rank deficient. The rank deficient matrix $A$ maps $x$ to $y$ and this transformation is neither onto (points in the $y_1 - y_2$ plane not on the line $y_2 = 2y_1$ e.g. $(2,3)$ are not mapped onto, which results in no solutions) nor one-to-one (every point $(c,2c)$ on the line $y_2 = 2y_1$ corresponds to the line $x_1 + 2x_2 =c$ in the $x_1 - x_2$ plane, which results in infinite solutions).
An observation you can make here is that the product of the slopes of the line $x_1 + 2x_2 = c$ and $y_2 = 2y_1$ is $-1$. This is true in general for higher dimensions as well.
From an applied setting, rank of a matrix denotes the information content of the matrix. The lower the rank, the lower is the "information content". For instance, when we say a rank $1$ matrix, the matrix can be written as a product of a column vector times a row vector i.e. if $u$ and $v$ are column vectors, the matrix $uv^T$ is a rank one matrix. So all we need to represent the matrix is $2n-1$ elements. In general, if we know that a matrix $A \in \mathbb{R}^{m \times n}$ is of rank $p$, then we can write $A$ as $U V^T$ where $U \in \mathbb{R}^{m \times p}$ and is of rank $p$ and $V \in \mathbb{R}^{n \times p}$ and is of rank $p$. So if we know that a matrix $A$ is of rank $p$ all we need is only $2np-p^2$ of its entries. So if we know that a matrix is of low rank, then we can compress and store the matrix and can do efficient matrix operations using it. The above ideas can be extended for any linear operator and these in fact form the basis for various compression techniques. You might also want to look up Singular Value Decomposition which gives us a nice (though expensive) way to make low rank approximations of a matrix which allows for compression.
From solving a linear system point of view, when the square matrix is rank deficient, it means that we do not have complete information about the system, ergo we cannot solve the system.
I think your "proof by cases" works just fine, though I personally would do three cases, with first case "if $k < m \implies$ Contradiction", basically, then writing the very reasons you concluded that $k \geq m$.
Note: That's just how I'd do it, since you are already considering cases, we might as well exhaust them all, which you did (consider them all, just not explicitly so).
But my preference has nothing to do with the correctness of your proof. Your logic, which you included, for good reason, does the job.
Best Answer
It’s highly compressed and very sloppy; I’ll try to expand it. I’ll assume that you’re working over the field of real numbers. Let $A$ be an $n\times n$ matrix of rank $1$. This means that $\{Ax:x\in\Bbb R^n\}$ is a one-dimensional vector space, so it has a one-element basis $\{b\}$. This means that every vector $Ax$ is a scalar multiple of that basis vector $b$, so for each $x\in\Bbb R^n$ there is a scalar $\lambda(x)\in\Bbb R$ such that $Ax=\lambda(x)b$.
For $k=1,\ldots,n$ let $e_k$ be the $n\times 1$ matrix with a $1$ in the $k$-th row and zeroes everywhere else, and let $c=\begin{bmatrix}\lambda(e_1)&\lambda(e_2)&\ldots&\lambda(e_n)\end{bmatrix}^T$. If $x=\begin{bmatrix}x_1&x_2&\ldots&x_n\end{bmatrix}^T$, then $x=\sum_{k=1}^nx_ke_k$, and multiplication by $A$ is a linear transformation, so
$$\begin{align*} Ax&=A\sum_{k=1}^nx_ke_k=\sum_{k=1}^nx_kAe_k=\sum_{k=1}^nx_k\lambda(e_k)b\\ &=\left(\begin{bmatrix}\lambda(e_1)&\lambda(e_2)&\ldots&\lambda(e_n)\end{bmatrix}\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}\right)b\\ &=\left(c^Tx\right)b\;. \end{align*}$$
Thus, for each $x\in\Bbb R^n$ we have $\lambda(x)b=Ax=c^Txb$, so $\lambda(x)=c^Tx$. Now $c^Tx$ is a scalar, so
$$Ax=\left(c^Tx\right)b=b\left(c^Tx\right)=\left(bc^T\right)x$$
for each $x$, and $bc^T$ is an $n\times n$ matrix, so $A=bc^T$.