When finding the Smith Normal Form of a given matrix $A$, I do not understand why we can assume $(A_{11})$ is the $\gcd$ of all the entries of the matrix $A$, i.e., how can we generate the $\gcd$ of all the entries (performing elementary columns and row operations) and put it in the position $(1,1)$ of the matrix?
Construction of the Smith Normal Form of a matrix
abstract-algebralinear algebrasmith-normal-form
Related Solutions
To expand my comment...Add column 2 to column 1. Subtract row 2 from row 1. Now you have a scalar in the (1,1) position -- rescale to 1.
$$\begin{pmatrix} x-3 & 0 & 0 & 0 \\ 0 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim \begin{pmatrix} x-3 & 0 & 0 & 0 \\ x+1 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim $$ $$\begin{pmatrix} -4 & -x-1 & 0 & 0 \\ x+1 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim \begin{pmatrix} 1 & (1/4)(x+1) & 0 & 0 \\ x+1 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim $$
Now add $(-1/4)(x+1)$ times column 1 to column 2 (to clear everything beside 1).
$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ x+1 & x+1-(1/4)(x+1)^2 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim $$
Add $-(x+1)$ times row 1 to row 2 (to clear everything below 1) & simplify the (2,2)-entry. Then rescale row 2 (so the polynomial is monic).
$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & -(1/4)(x+1)(x-3) & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & (x+1)(x-3) & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & x+1\end{pmatrix} \sim $$
Finally swap columns 2 and 4 and then rows 2 and 4 to switch the positions of $(x+1)(x-3)$ and $x+1$. We are left with the Smith normal form.
$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & (x+1)(x-3)\end{pmatrix} $$
I'll answer your second question first.
Let
$$P(x) = \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&(x-2)^2&0\\0&0&0&(x-1)(x-2)\end{bmatrix}.$$
We need to fix the bottom right $2 \times 2$ principal submatrix. I have explained how to do that here, so I'll just present the results here:
\begin{align*} \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&(x-2)^2&0\\0&0&0&(x-1)(x-2)\end{bmatrix} &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&(x-2)^2&(x-1)(x-2)\\0&0&0&(x-1)(x-2)\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&(x-2)^2&(x-2)^2+(x-2)\\0&0&0&(x-1)(x-2)\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&(x-2)^2&x-2\\0&0&0&(x-1)(x-2)\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&x-2&(x-2)^2\\0&0&(x-1)(x-2)&0\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&x-2&0\\0&0&(x-1)(x-2)&-(x-1)(x-2)^2\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&x-2&0\\0&0&0&-(x-1)(x-2)^2\end{bmatrix} \\ &\mapsto \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&x-2&0\\0&0&0&(x-1)(x-2)^2\end{bmatrix} \end{align*}
Irreducible factors are $x-2$ and $x-1$, while the elementary divisors are $x-2$, $(x-2)^2$ and $x-1$.
I think, but I'm not sure, that what you suggest in your first question can always be done to obtain the correct result. One would have to prove it to actually use it. Personally, I find it easier to just properly reduce the matrix polynomial or to fix it to become the Smith normal form, like I did above.
Best Answer
Using the Euclidean algorithm on rows/columns, first ensure that $A_{11}$ divides all entries $A_{i1}$ in the same column, and then use this to set all $A_{i,1}:=0$ (for $i>1$). Ditto for the row $A_{1i}$. Now suppose there is an entry $A_{ij}$ (for $i,j>1$) that is not divisible by $A_{11}$. Then add the $i$-th row to the first, this keeps $A_{11}$ the same and sets $A_{1j}=A_{ij}$. return to cleaning out row $1$.