How does a linear operator act on vectors that are not eigenvectors of the operator? I feel like I have the wrong end of the stick in thinking about quantum state vectors, and so wish to try and clear this up.
If I prepare a single spin in the up state (along the z-dimension), and repeatedly measure the spin in this direction, I will repeatedly obtain +1 due to the up vector being an eigenvector of the z-spin operator, with eigenvalue +1?
My question is if I then measure the component of spin along the x-direction, I will randomly obtain +1 or -1, but what state is the system left in. The up vector is not an eigenvector of the x-spin operator, and there does not exist an eigenvalue with which the outcome of measurement can be.
I feel like I am just missing something here so I would be very grateful if you could clear this up.
 A: When you measure an observable of a system which is in a definite eigenstate of said observable, you will always find the associated eigenvalue, as you know.
General states in quantum mechanics are almost never eigenstates of an observable. But all states can be represented as a linear combination of those eigenstates. For your problem we can say $|\psi> = a|\uparrow_x> + b |\downarrow_x>$, with the arrows indicating the direction and the $x$ subscript denoting that we are talking relative to the $x$ direction.
When you measure such a state, the system will 'collapse' into an eigenstate and you will measure the associated eigenvalue. By 'collapse' we mean that the state changes abruptly from a linear combination of eigenstates to a single, definite eigenstate. There is no way to predict which eigenstate it will collapse into. The best you can do is predict the probability to collapse into a specific eigenstate. More specifically, if the above $|\psi>$ was properly normalized, the probability for the system to collapse into $|\uparrow_x>$ is $a^2$ and the probability for the system to collapse into $|\downarrow_x>$ is $b^2$.
See also the Measurement Problem in quantum mechanics.
A: The system is left in whichever eigenstate of the spin in x-direction operator it ended up after the measurement. The state of the system will be a superposition state with respect to the z-direction angular momentum.
When you say "the up operator", you presumably mean the $S_z$ operator. It's true that its eigenstates are not eigenstates of the $S_x$ operator. However the eigenstates of $S_z$ could be expressed in terms of the eigenstates of the $S_x$ with a change of basis. You could subsequently measure $S_x$. 
