For every n-dimensional vector space there does exist a basis consisting of semi-definite matrices.
Proof: Take the canonical basis of the vector space. This is where we have matrices {E11,E12,...,E1n,E21,E22,...,E2n,...,...,En1,En2,...,Enn} where Eij is a matrices with all zero elements except the (i,j) entry.
All these matrices are semi-definite.
As the characteristic polynomial is x^n for all Eij where i is not equal to j and the characteristic poly is x^(n-1) * (x-1) for Eii 1<=i<=n.
Now all eigenvalues of a matrix are the roots of the characteristic poly i.e (in this case) just 0 and 1. So the matrices are all semi-definite.
Hope this helps.
AT