Your answer is partially correct. For instance
$$
A=\left( {\begin{array}{*{20}{c}}
2 & 0 & 1 \\
0 & { - 1} & 0 \\
0 & 0 & { - 1} \\
\end{array}} \right) \in M_3
$$
is not in the span of your basis because $a_{1,3} \ne 0$ but $trace(A)=0$. When $n=2$ your subspace is
$$\begin{align} M_2 &=\left\{ \left( {\begin{array}{*{20}{c}}
a & b \\
c & d \\
\end{array}} \right) | a,b,c,d \in \mathbb{R},a+d=0
\right\} \\
&=\left\{ \left( {\begin{array}{*{20}{c}}
a & b \\
c & {-a} \\
\end{array}} \right) | a,b,c \in \mathbb{R}
\right\} \\
&=\left\{ a \left( {\begin{array}{*{20}{c}}
1 & 0 \\
0 & {-1} \\
\end{array}} \right) + b\left( {\begin{array}{*{20}{c}}
0 & 1 \\
0 & 0 \\
\end{array}} \right)+
c\left( {\begin{array}{*{20}{c}}
0 & 0 \\
1 & 0 \\
\end{array}} \right)| a,b,c \in \mathbb{R}
\right\}
\end{align}$$
so a a natural basis for $M_2$ is
$$B=\left\langle \left( {\begin{array}{*{20}{c}}
1 & 0 \\
0 & {-1} \\
\end{array}} \right), \left( {\begin{array}{*{20}{c}}
0 & 1 \\
0 & 0 \\
\end{array}} \right),
\left( {\begin{array}{*{20}{c}}
0 & 0 \\
1 & 0 \\
\end{array}} \right)
\right\rangle.$$
So $dim(M_2)=3=2*2-1$. To extend above idea, we have for $n \in \mathbb{N}$
$$\begin{align} M_n &=\left\{ \left( {\begin{array}{*{20}{c}}
{{a_{1,1}}} & \cdots & {{a_{1,n}}} \\
\vdots & \ddots & \vdots \\
{{a_{n,1}}} & \cdots & {{a_{n,n}}} \\
\end{array}} \right) | \sum\limits_{j=1}^{n}{a_{j,j}}=0
\right\} \\
&=\left\{ \left( {\begin{array}{*{20}{c}}
{{a_{1,1}}} & \cdots & {{a_{1,n}}} \\
\vdots & \ddots & \vdots \\
{{a_{n,1}}} & \cdots & {{a_{n,n}}} \\
\end{array}} \right) | a_{n,n}=-\sum\limits_{j=1}^{n-1}{a_{j,j}}
\right\} \\
&=\left\{ \left( {\begin{array}{*{20}{c}}
{{a_{1,1}}} & \cdots & {{a_{1,n}}} \\
\vdots & \ddots & \vdots \\
{{a_{n,1}}} & \cdots & {{\sum\limits_{j=1}^{n-1}{-a_{j,j}}}} \\
\end{array}} \right)
\right\} \\
&=\left\{ {{a_{1,1}}\left( {\begin{array}{*{20}{c}}
1 & 0 & \cdots & 0 \\
0 & \vdots & \vdots & \vdots \\
\vdots & \vdots & \vdots & 0 \\
0 & \ldots & 0 & { - 1} \\
\end{array}} \right) + {a_{1,2}}\left( {\begin{array}{*{20}{c}}
0 & 1 & 0 & 0 \\
0 & 0 & \vdots & \vdots \\
\vdots & \vdots & \vdots & 0 \\
0 & \ldots & 0 & { - 1} \\
\end{array}} \right) + \cdots + {a_{n,n - 1}}\left( {\begin{array}{*{20}{c}}
0 & 0 & \cdots & 0 \\
0 & \vdots & \vdots & \vdots \\
\vdots & \vdots & 0 & 0 \\
0 & \vdots & 1 & { - 1} \\
\end{array}} \right)} \right\}
\end{align}
$$
and a natural basis for $M_n$ is
$$B={\left\langle {\left( {\begin{array}{*{20}{c}}
1 & 0 & \cdots & 0 \\
0 & \vdots & \vdots & \vdots \\
\vdots & \vdots & \vdots & 0 \\
0 & \ldots & 0 & { - 1} \\
\end{array}} \right),\left( {\begin{array}{*{20}{c}}
0 & 1 & 0 & 0 \\
0 & 0 & \vdots & \vdots \\
\vdots & \vdots & \vdots & 0 \\
0 & \ldots & 0 & { - 1} \\
\end{array}} \right), \cdots ,\left( {\begin{array}{*{20}{c}}
0 & 0 & \cdots & 0 \\
0 & \vdots & \vdots & \vdots \\
\vdots & \vdots & 0 & 0 \\
0 & \vdots & 1 & { - 1} \\
\end{array}} \right)} \right\rangle }
$$
hence $dim(M_n)=n^2 -1$.
What you did is a correct way to do it. By definition, rank of a matrix is dimension of row/column space (it is a theorem that these are equal), i.e. for matrix $(v_1\ v_2\ \ldots\ v_n)$, where $\{v_1,\ldots,v_n\}$ are column vectors, $\operatorname{rank}(v_1\ v_2\ \ldots\ v_n) = \dim\operatorname{span}\{v_1,\ldots,v_n\}$.
However, there is no need to transpose matrix back and forth. Rank of matrix is invariant under Gaussian elimination of either rows or columns. In practice, it is enough to produce upper triangular matrix using Gaussian elimination and count non-zero rows. Thus, you could have done something like this:
$$\begin{pmatrix}
1 & 4 & 6\\
3 & 5 & 4\\
5 & 6 & 2
\end{pmatrix}\sim \begin{pmatrix}
1 & 4 & 6\\
0 & -7 & -14\\
0 & -14 & -28
\end{pmatrix}\sim \begin{pmatrix}
1 & 4 & 6\\
0 & -7 & -14\\
0 & 0 & 0
\end{pmatrix}$$
Best Answer
You can just try some small numbers, easiest to play with $1$ and $0$.
For $N(T)$, as you started you get these $3$ equations ($2$ of them are the same) as $-a_{11}-a_{12} =a_{13}$, so that $a_{11}$, $a_{12}$ and $a_{21}$, $a_{22}$ can be anything, only $a_{13}$ and $a_{23}$ are bound to them. Also, $a_{31},\ a_{32},\ a_{33}$ can be anything.
So, consider these elements of $N(T)$: