On the determinant of a certain matrix over the polynomial ring of $n$ variables over a field 
Let $A = k[x_1,\dots, x_n]$ be a polynomial ring over a field $k$.
  Let $\sigma_1,\dots,\sigma_n$ be distinct permutations of the set $\{1,\dots,n\}$.
  Is the determinant det$(x_{\sigma_i(j)})$ non-zero in $A$?

The motivation came from one of the proofs of the normal basis theorem on a finite Galois extension of a field. 

Let $K/k$ be a finite Galois extension of a field $k$, $G$ its Galois group. Let $\sigma_1, \dots, \sigma_n$ be the elements of $G$. We assign a variable $x_i$ for each $\sigma_i$. The proof uses the fact that det$(x_{\sigma_i\sigma_j}) \ne 0$ in $k[x_1,\dots,x_n]$, where we identify $x_i$ with $x_{\sigma_i}$.

I also want to know a proof of this fact.
 A: No. Set $n=4$ and take the following permutations: $\sigma_1=e$, $\sigma_2=(1\ 2)$, $\sigma_3=(3\ 4)$, and $\sigma_4=(1\ 2)(3\ 4)$.
For the second part of the question notice the following: since $\sigma_i\sigma_j\in G$ there is $a_{ij}\in\{1,\dots,n\}$ such that $\sigma_i\sigma_j=\sigma_{a_{ij}}$. Moreover, $a_{ij_1}\ne a_{ij_2}$ for $j_1\ne j_2$, and $a_{i_1j}\ne a_{i_2j}$ for $i_1\ne i_2$. (If $a_{ij_1}=a_{ij_2}$, then $\sigma_i\sigma_{j_1}=\sigma_i\sigma_{j_2}$ and therefore $\sigma_{j_1}=\sigma_{j_2}$, so $j_1=j_2$.) This shows that the row and the column indices of the matrix $(x_{a_{ij}})$ represent distinct permutations of $\{1,\dots,n\}$.
Now suppose $\det(x_{\sigma_i\sigma_j})=0$. Then, for $x_1=1$, and $x_2=\cdots=x_n=0$ we get the determinant of a $0,1$ matrix which is necessarily equal to zero. But how does this matrix look like? Well, it has a $1$ on each row (and the other $n-1$ entries are $0$). Now we wonder whether two $1$'s can be on the same column, and the answer is no. (Why?) But such a matrix has non-zero determinant, being a permutation matrix (that is, a matrix obtained from the unit matrix by permuting its rows and columns).
A: Counterexample to the first question: Set $n = 5$, and let $\sigma_1, \sigma_2, \ldots, \sigma_5$ be five distinct permutations fixing $4$ and $5$ (there are six such permutations in total, and you are free to pick any five of them). The matrix will then have its fourth column filled with $x_4$'s and its fifth column filled with $x_5$'s; this does not bide well for its determinant.
The second question is really about finite groups, not about Galois groups. You can have $G$ be any finite group. Your determinant is $\Theta\left(G\right)$ in the notations of Keith Conrad's paper The origin of representation theory. You thus want to prove that $\Theta\left(G\right) \neq 0$. (Indeed, $\Theta\left(G\right)$ is plus-minus your determinant.) In §5 of this paper, it is shown that the polynomial $\Theta\left(G\right)$ is a product of polynomials that are monic in $X_e$ (where $e$ is the identity of $G$), and thus itself is monic in $X_e$. Now there is a subtlety involved, because Keith Conrad works over $\mathbb{C}$ rather than an arbitrary field $k$. But this is no big deal, because once you know that the polynomial $\Theta\left(G\right)$ is monic in $X_e$ when seen as a polynomial over $\mathbb{C}$, you automatically conclude that the same holds over any field (or commutative ring $k$), because the polynomial $\Theta\left(G\right)$ is defined over $\mathbb{Z}$.
Actually, here is a simpler answer to your second question: The determinant $\left(x_{gh}\right)_{g\in G,\ h \in G}$, expanded using the Leibniz formula, contains (up to sign) the addend $\prod_{g \in G} x_{gg^{-1}} = \prod_{g \in G} x_e = x_e^{\left|G\right|}$, where $e$ is the identity of $G$. No other addend of the expansion of the determinant contains this high a power of $x_e$. Hence, this determinant (as a polynomial in the $x_g$) has a nonzero coefficient in front of $x_e^{\left|G\right|}$, and thus is nonzero.
