Where $\sigma \in S_n$ and the representation is over the vector space $\mathbb{C}^n$
I'm trying to find as many invariant subspaces of this representation as possible. I don't know how to find these invariant subspaces other than the guess and check method - so far I have these two:
$$\{[x_1,...,x_n] \in \mathbb{C}^n | \sum_{i=1}^n x_i = 0\}$$
and
$$\{[x_1,...,x_n] \in \mathbb{C}^n | x_1 = x_2 = ... = x_n\}$$
Are there any others? Is there a way of proving that there are (or aren't) any others? Is there a good method of finding these?
In general the approach seems to be to construct the matrix of the representation and find the eigenspaces, but I don't see how to do that with this particular representation. Is it possible?
In general, given a complex finite dimensional representation of a finite group, you can always use character theory to work out which irreducible representations of the group appear as subrepresentations of the given one, and with which multiplicity. You can even find the actual subspaces, using projection idempotents.
In your particular example, the two you have found are the only ones. The general theorem is that if a group $G$ acts doubly transitively on a set $X$, meaning that $G$ acts transitively and for every $x\in X$, the stabiliser ${\rm Stab}_{G}(x)$ acts transitively on $X\setminus \{x\}$, then the permutation representation $\mathbb{C}[X]$ has exactly one copy of the trivial representation, and the complement is irreducible.
You can find this in every introductory text book on representation theory, or in my notes. The business about permutation representations is treated in section 5.