Under fair use for pedagogic purposes, the following is taken (often, but not always, verbatim) from Bethe and Jackiw, Intermediate Quantum Mechanics.
We take the metric $g$ as $$ g(\mu,\nu) = \begin{cases} +1&\mu=\nu = 0, \\ -1&\mu=\nu \in \left\{1,2,3\right\}, \\ 0&\text{otherwise}. \end{cases} $$
We now obtain several theorems about the Dirac matrices. The fundamental relationship for the Dirac matrices is \begin{equation*} \label{eq:sartrywere} \gamma^\mu\gamma^\nu + \gamma^\mu\gamma^\nu = 2\,g^{\mu\nu} \quad \text{and} \quad \gamma_\mu\gamma_\nu + \gamma_\mu\gamma_\nu = 2\,g_{\mu\nu} \tag{1} \end{equation*} Equation (1) is the condition of a Clifford algebra.
We now form $2^4$ matrices from the four matrices $\gamma^\mu$ with the following products: \begin{equation} \label{eq:sfwergerger} k_{\left(d_0,d_1,d_2,d_3\right)}\, {\gamma^{\sigma(0)}}^{d_0} {\gamma^{\sigma(1)}}^{d_1} {\gamma^{\sigma(2)}}^{d_2} {\gamma^{\sigma(3)}}^{d_3} , \end{equation} where $\left(d_0,d_1,d_2,d_3\right)\in\left\{\left(0,0,0,0\right),\left(0,0,0,1\right),\ldots, \left(1,1,1,1\right)\right\}$, $k_{\left(d_0,d_1,d_2,d_3\right)}\in \mathbb{C}\!\setminus \!\left\{0\right\}$, and $\sigma$ is any permutation of $\left(0,1,2,3\right)$. Since the square of each $\gamma^\mu$ equals to $\pm I_4$, we consider only these $4^2$ matrices. Any other product formed with additional multiples of these matrix will be equivalent to one of these $4^2$ matrices up to a multiplicative constant. The order of the factors is immaterial since different matrices either commute or anticommute. Though not necessary, we will enumerate the matrices in the following way. \begin{align*} \Gamma_1 &= I_4, \\ \Gamma_2 &= \gamma^0, \\ \Gamma_3 &= i\gamma^1, \\ \Gamma_4 &= i\gamma^2, \\ \Gamma_5 &= i\gamma^3, \\ \Gamma_6 &= \gamma^0\gamma^1, \\ \Gamma_7 &= \gamma^0\gamma^2, \\ \Gamma_8 &= \gamma^0\gamma^3, \\ \Gamma_9 &= i\gamma^2\gamma^3, \\ \Gamma_{10} &= i\gamma^3\gamma^1, \\ \Gamma_{11} &= i\gamma^1\gamma^2, \\ \Gamma_{12} &= i\gamma^0\gamma^2\gamma^3, \\ \Gamma_{13} &= i\gamma^0\gamma^3\gamma^1, \\ \Gamma_{14} &= i\gamma^0\gamma^1\gamma^2, \\ \Gamma_{15} &= \gamma^1\gamma^2\gamma^3, \\ \Gamma_{16} &= i \gamma^0\gamma^1\gamma^2\gamma^3. \end{align*}
Theorem 1
- For all pairs $(l,m)$ there exists an $a_{lm}$, where $a_{lm}$ equals $+1$, $+i$, $-1$, or $-i$, such that $\Gamma_l\,\Gamma_m = a_{lm}\,\Gamma_n$.
- $\Gamma_l\,\Gamma_m = I$ if, and only if, $l=m$.
- $\Gamma_l\,\Gamma_m = \pm \Gamma_m \,\Gamma_l $.
- If $\Gamma_l \neq I$, then there always exists a $\Gamma_k$ such that $$\Gamma_k\,\Gamma_l\,\Gamma_k = -\Gamma_l.$$
Proof: These items will be left for the reader to verify.
Theorem 2
For all $l\in\left\{2,\ldots, 16\right\}$ $$ \operatorname{Tr}\left(\Gamma_l\right) = 0. $$
Proof:
Choose a $k$ such that by applying the second item above and the fourth items above we have \begin{align} \operatorname{Tr}\left(\Gamma_l\right) &= \operatorname{Tr}\left(\Gamma_l\,I\right) \\ &= \operatorname{Tr}\left(\Gamma_l\,\Gamma_k\,\Gamma_k\right) &&\text{2nd Item} \\ &= \operatorname{Tr}\left(\Gamma_k\,\Gamma_l\,\Gamma_k\right) &&\text{3rd item} \\ &= \operatorname{Tr}\left(-\Gamma_l\right) &&\text{4th item} \\ &= - \operatorname{Tr}\left(\Gamma_l\right) \end{align} By the transitive property of the equality $- \operatorname{Tr}\left(\Gamma_l\right) = \operatorname{Tr}\left(\Gamma_l\right) $. Thus $ \operatorname{Tr}\left(\Gamma_l\right) =0$ for all the $\Gamma$'s except $\Gamma_1$, which is equal to $I$.
Theorem 3 $$ \sum_{k=1}^{16} x_k\,\Gamma_k = 0 $$ if, and only if, $x_1 = x_2 = \cdots = x_{16}$.
Proof
Choose an arbitrary $m$ and multiply as follows $$ \Gamma_m\sum_{k=1}^{16} x_k\,\Gamma_k = x_m \Gamma_m\Gamma_m + \Gamma_m\sum_{\substack{k=1\\k\neq m}}^{16} x_k\,\Gamma_m \Gamma_k = \Gamma_m\,0. $$ Using the first and second item we have $$ x_m\,I + \Gamma_m\sum_{\substack{k=1\\k\neq m}}^{16} x_k\,a_{mk}\,\Gamma_n = 0. $$ Taking the trace we have that $$ x_m \,\operatorname{Tr}(I) = 0. $$ We must have that $x_m=0$. Since $m$ was arbitrary, symmetrical arguments can be made for each of the sixteen $\Gamma$'s. Since by definition the sequence of vectors $ \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{n}$ is said to be linearly independent if the equation $$ a_{1}\mathbf {v} _{1}+a_{2}\mathbf {v} _{2}+\cdots +a_{n}\mathbf {v} _{n}=\mathbf {0} , $$ can only be satisfied by a $ a_{i}=0$ for $i=1,\dots ,n$, therefore the $\Gamma$'s are linearly indepdendent.
Corollary 1 The $\Gamma$'s cannot be represented by matrices whose dimension is less than 4-x-4.
Proof: It is impossible to construct 16 linearly independent matrices from matrices with whose dimension is less that $4^2$.
Corollary 2 There exists precisely 16 linear independent 4-x-4 which we can use to represent the 16 $\Gamma$'s.
Proof: It is impossible to construct 16 linearly independent matrices from matrices with whose dimension is less that $4^2$.
p.s. Regarding the question "Why is the basis constructed of the totally antisymmetric gamma matrices and not the totally symmetric ones?", I frankly do not understand what you mean by this. All I will say is that there is no unique representation of the $\Gamma$ matrices.
References
Bethe and Jackiw, Intermediate Quantum Mechanics, pp. 354-6.