In my university we defined tensor product of two matrices $A$, $B$ as a matrix $A \otimes B$ such that for any vectors $\left| \phi \right>$, $\left| \psi \right>$ the following is satisfied: $$ \displaystyle (A \otimes B) (\left| \phi \right> \otimes \left| \psi \right>) = (A \left| \phi \right>) \otimes (B \left| \psi \right>). $$ Imagine we have 2 qubits and we want to apply to them some gates in parallel f.e. Hadamard $H$ to $q_0$ and $X$ to $q_1$ as in image below.
I was told that in order to obtain a single 4 by 4 matrix, which applies both of these gates in parallel to a 2 qubit state vector, I have to take a tensor product $H \otimes X$. In the case when the input is in separable state and I can write it as a product of two states of single qubits, it is clear for me that the above definition of the tensor product justifies this. In our example if the state on the input is $\left| q_0 \right> \otimes \left| q_1 \right>$, we can write
$$ \displaystyle (H \otimes X) (\left| q_0 \right> \otimes \left| q_1 \right>) = (H \left| q_0 \right>) \otimes (X \left| q_1 \right>), $$ so multiplying by $H \otimes X$ is as though we were applying each of those gates to the single corresponding qubit - $H$ to $\left | q_0 \right>$ and $X$ to $\left | q_1 \right>$.
The question: Why is taking tensor product of gate matrices in order to produce appropriate matrix for parallel gates still justified when the input is in entangled state? Because we cannot write a state as a product of single qubit states, the defining property of the tensor product doesn't tell us why the product matrix is the correct one for operations in parallel.
To sum up:
Input is a separable state - the use of the tensor product is undeniably correct, because of its defining property
Input is an entangled state - why the same tensor product of matrices works for parallel gates? Does it have some meaning or is it just an extrapolation?