# Famous Theorems of Mathematics/Algebra/Matrix Theory

An m×n matrix M is a function $M:A\rightarrow F$ where A = {1,2...m} × {1,2...n} and F is the field under consideration.
An m×n matrix (read as m by n matrix), is usually written as:
    $A=\left({\begin{matrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{matrix}}\right)$
For other related definitions please see this link.

## Basic Proofs

1. The set of all m×n matrices forms an abelian group under matrix addition.
    Proof: Clearly the sum of two m×n matrices is another m×n matrix. If A and B are two matrices of equal order then working with their (i,j)th entries we have $(A+B)_{i,j}=(A_{i,j})+(B_{i,j})=(B_{i,j})+(A_{i,j})=(B+A)_{i,j}$ which proves A+B = B+A i.e. commutativity. For associativity we proceed similarly so that A + (B + C) = (A + B) + C. Also the m×n matrix with all entries zero is the additive identity. For every matrix A, the matrix -A whose (i,j)th entry is $-A_{i,j}$ is the inverse. So matrices of same order form an abelian group under addition.
2. Scalar Multiplication has the following properties:
       1. Left distributivity: (α+β)A = αA+βA.
       2. Right distributivity: α(A+B) = αA+αB.
       3. Associativity: (αβ)A=α(βA)).
       4. 1A = A.
       5. 0A= 0.
       6. (-1)A = -A.
       (0,1,-1,α & β are scalars; A & B are matrices of equal order, 0 is the zero matrix.)
    Proof: Start with the left hand side of (1). We will work with the (i,j)th entries. Clearly $((\alpha +\beta )A)_{i,j}=(\alpha +\beta )\cdot A_{i,j}=(\alpha A)_{i,j}+(\beta A)_{i,j}$ and so (1) is proved. Similarly (2) can be proved. Associativity follows as $((\alpha \beta )A)_{i,j}=(\alpha \beta )\cdot A_{i,j}=\alpha (\beta A_{i,j})$. (4), (5) and (6) follow directly from the definition.
3. Matrix multiplication has the following properties:
       1. Associativity: A(BC) = (AB)C.
       2. Left distributivity: A(B+C) = AB+AC.
       3. Right distributivity: (A+B)C = AC+BC.
       4. IA = A = AI.
       5. α(BC) = (αB)C = B(αC).
       (α is a scalar; A, B & C are matrices, I is the identity matrix. A,B,C & I are of orders m×n, n×p, p×r & m×m respectively.)
    Proof: We work with the (i,j)th entries and prove (1) only. The proofs for the rest are similar. Now $(A(BC))_{i,j}=\sum _{k=1}^{n}A_{i,k}(BC)_{k,j}=\sum _{k=1}^{n}A_{i,k}{\Big\sum _{l=1}^{p}B_{k,l}C_{l,j}{\Big )}=\sum _{k=1}^{n}\sum _{l=1}^{p}A_{i,k}B_{k,l}C_{l,j}$ and also $((AB)C)_{i,j}=\sum _{l=1}^{p}(AB)_{i,l}C_{l,j}=\sum _{l=1}^{p}{\Big\sum _{k=1}^{n}A_{i,k}B_{k,l}{\Big )}C_{l,j}=\sum _{k=1}^{n}\sum _{l=1}^{p}A_{i,k}B_{k,l}C_{l,j}$ so that (i,j)th entries on the two sides are equal.
4. Let A and B be m×n matrices. Then:
    (i) $(kA)^{T}$ = $kA^{T}$
    (ii) $(A+B)^{T}=A^{T}+B^{T}$
    (iii) $(AB)^{T}=B^{T}A^{T}$
    Sketch of Proof: Work with the (i,j) entries as in the previous proofs.
5. Any system of linear equations has either no solution, exactly one solution or infinitely many solutions.
    Proof: Suppose a linear system Ax = b has two different solutions given by X and Y. Then let Z = X - Y. Clearly Z is non zero and A(X + kZ) = AX + kAZ = b + k(AX - AY) = b + k(b - b) = b so that X + kZ is a solution to the system for every possible value of k. Since k can assume infinitely many values so clearly we have an infinite number of solutions.
6. Any triangular matrix A satisfying $AA^{T}=A^{T}A$ is a diagonal matrix.
    Proof: Suppose A is lower triangular. Now the (i,i)th entry of $AA^{T}$ is given by $\sum _{k=1}^{n}(A_{i,k})(A_{k,i}^{T})=\sum _{k=1}^{n}(A_{i,k})(A_{i,k})=\sum _{k=1}^{n}(A_{i,k}^{2})=\sum _{k=1}^{i}(A_{i,k}^{2})$. Also the (i,i)th entry of $A^{T}A$ is given by $\sum _{k=1}^{n}(A_{i,k}^{T})(A_{k,i})=\sum _{k=1}^{n}(A_{k,i})(A_{k,i})=\sum _{k=1}^{n}(A_{k,i}^{2})=\sum _{k=i}^{n}(A_{k,i}^{2})$. Now as $AA^{T}=A^{T}A$ so $\sum _{k=1}^{i}(A_{i,k}^{2})=\sum _{k=i}^{n}(A_{k,i}^{2})$ and as $A_{i,i}^{2}$ can be subtracted from the two sides we are left with $\sum _{k=1}^{i-1}(A_{i,k}^{2})=\sum _{k=i+1}^{n}(A_{k,i}^{2})$.
Now if i = 1 then we have $0=A_{2,1}^{2}+A_{3,1}^{2}\cdots A_{n,1}^{2}$ which gives us $A_{2,1}=A_{3,1}\cdots A_{n,1}=0$. Similarly for i =2 we have $0=A_{2,1}^{2}=A_{3,2}^{2}+A_{4,2}^{2}\cdots A_{n,2}^{2}$ so that $A_{3,2}=A_{4,2}\cdots A_{n,2}=0$. It is now clear that in this fashion all non diagonal entries of A can be shown to be zero. The proof for an upper triangular matrix is similar.