Can This Matrix Proof Be Done Without the Definition?

Question

The following was taken from Stephen Friedberg's Linear Algebra, 2nd Edition.

Let $A$ be a $m \times n$ matrix, $B$ and $C$ be $n \times p$ matrices.
Show that $A(B+C) = AB + BC$ and, for any $k \in F$, $k(AB) = (kA)B = A(kB)$.

Proof: $[ A(B+C) ]_{ij} = \sum_{i=1}^n A_{ik}(B+C)_{kj}$
$= \sum_{i=1}^n A_{ik}B_{kj} + \sum_{i=1}^n A_{ik}C_{kj} = (AB)_{ij} + (BC)_{ij} = [AB + BC]_{ij}$

I did the second part myself: We have $[k(AB)]_{ij} = k \sum_{i=1}^n A_{ik}B_{kj}$
$ = \sum_{i=1}^n kA_{ik}B_{kj} = \sum_{i=1}^n (kA)_{ik}B_{kj}$
$ = \sum_{i=1}^n A_{ik}kB_{kj} = \sum_{i=1}^n A_{ik}(kB)_{kj}$
As a result, $k(AB) = (kA)B = A(kB)$.

I noticed that the proof used the definition of matrix addition and scalar multiplication. $(B+C)_{ij} = B_{ij} + C_{ij}$ and $(kA)_{ij} = k(A)_{ij}$. Now is it possible to prove without the definitions?
I became curious because Mr. Friedberg introduced the matrix as a representation of a linear transformation over an ordered basis. So, I tried proving via the linear transformation over an ordered basis and could not do it. For example:

Let $\alpha = \{x_1, x_2 ... x_n\}$ be an ordered basis of $V, \gamma = \{z_1, z_2 ... z_m\}$ be an ordered basis of $W$,
and $T: V \rightarrow W$ be a linear transformation. Elsewhere, Mr. Friedberg already defined that $(kT)(x_j) = kT(x_j)$. Suppose that $A$ is the matrix representation of $T$.

$k(A) = k *[ \space T(x_1) \space T(x_2) \space ... \space T(x_n) \space ] = [\space kT(x_1) \space kT(x_2) \space ... \space kT(x_n) \space ] = [ \space (kT)(x_1) \space (kT)(x_2) \space ... \space (kT)(x_n) \space]$

But this is possible only because of the definition of scalar multiplication.

I am confused what you are asking. Are you asking to show matrix multiplication distributes over matrix addition without defining what the operations are? — Owen Sizemore, Sep 01 '13 at 04:01
@OwenSizemore: Now that you frame the question this way, I can see how stupid my endeavor was. I guess I haven't fully understood the idea that a matrix is a linear transformation over an ordered basis. — Andy Tam, Sep 01 '13 at 04:26
This question is relevant: Proving Distributivity of Matrix Multiplication. — littleO, Sep 02 '13 at 02:17

score 1 · Answer 1 · answered Sep 02 '13 at 01:33

It's probably not possible to do so without using the definition directly. Given that we're including non-square matrices, we have the properties:

\begin{align*} A+B &= B+A & \text{addition is commutative} \\ A+(B+C) &= (A+B)+C & \text{addition is associative} \\ A+\mathbf{0} &= A & \text{existence of all-0 matrix} \\ \mathbf{0}+A &= A & \\ A+(-A) &= \mathbf{0} & \text{existence of additive inverse} \\ (-A)+A &= \mathbf{0} & \\ A(BC) &= (AB)C & \text{multiplication is associative} \\ (A+B)C &= AC+BC & \text{multiplication is right-distributive} \end{align*} and want to prove $A(B+C)=AB+AC$. If we input these as axioms into Mace4, we obtain the model:

$$ \begin{array}{c|cc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \qquad \begin{array}{c|cc} \times & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} $$ and we see that in this algebraic structure $1 \times (0+0)=1$ whereas $1 \times 0+1 \times 0=0$, so this algebraic structure does not have the left-distributive property.

Hence there is an algebraic structure which is consistent with all the above properties, but which is not left-distributive.

Hence, it is impossible to prove left-distributivity from the above axioms alone. (Any proof would equally disprove the existence of the above model, which exists.)

If we restrict to square matrices, we can add in the axioms:

\begin{align*} A+I &= A & \text{existence of identity} \\ I+A &= A & \\ \end{align*}

With this restriction the above model does not work; this time Mace4 gives the model: $$ \begin{array}{c|cc} + & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 1 & 2 & 3 \\ 1 & 1 & 0 & 3 & 2 \\ 2 & 2 & 3 & 0 & 1 \\ 3 & 3 & 2 & 1 & 0 \\ \end{array} \qquad \begin{array}{c|cc} \times & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 2 & 2 & 2 & 2 \\ 3 & 0 & 3 & 2 & 3 \\ \end{array} $$

We check $2 \times (0+0)=2$ and $2 \times 0 + 0 \times 2=0$. So again we have a non-left-distributive algebraic structure that satisfies all of the other axioms.

Caveat: It's possible that I've not included some axioms that would then allow left-distributivity to be proved (most notably axioms of scalar multiplication, which is not easy to input into Mace4). However, hopefully the message is still clear: it's likely there is an algebraic structure that is consistent with the remaining axioms (without being left-distributive), in which case those axioms are insufficient to prove left-distributivity.

Can This Matrix Proof Be Done Without the Definition?

1 Answers1