Suppose $\{a_1,a_2,\dots,a_n\}$ is a permutation of $\{1,2,\dots,n\}$. The probability of $a_i=j$ is estimated to be $p_{ij}$. The probability matrix might look like this
$$ P=\left( \begin{matrix} .2 & .1 & .2 & .5 \\ .4 & .3 & .3 & 0 \\ .2 & .3 & .2 & .3 \\ .2 & .3 & .3 & .2 \end{matrix} \right) $$
And it's now discovered that $a_1\neq1$ and $a_1 \neq 2$. How should I adjust the estimation?
My attempt to deal with this is to break $p_{ij}$ into the sum of the possibilities of $(n-1)!$ permutations where $a_i=j$, and I'll get 16 equations for 24 variables. $a_1\neq 1$ would mean that $P(1234)=P(1243)=P(1324)=P(1342)=P(1423)=P(1432)=0$, and it will affect other equations. But I don't know how to move on from here.
As far as I can tell, you simply don't have enough information to accurately update $P$. For instance, let's suppose when $n = 3$, we had $P_{ij} = 1/3$ for all $i, j$ and we found out that $a_1 \neq 1$ and $a_1 \neq 2$ (i.e. $a_1 = 3$).
Let's look at two cases that satisfy this $P$.
Case 1: All of the $3! = 6$ permutations are equally likely. In this case, we have that our updated $P$ should be: $$ P = \begin{bmatrix} 0 & 0 & 1 \\ 1/2 & 1/2 & 0 \\ 1/2 & 1/2 & 0 \end{bmatrix} $$
Case 2: Each of the permutations 123, 231, 312 have a $1/3$ probability (and all other permutations have zero probability). In this case our knowledge that $a_1 = 3$ dictates that our permutation is 312. We therefore have that $$ P = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} $$