@GeoffRobinson After I add the comment above, I realize that I am not so sure about the "If the matrix (aij) above is similar to a blocked upper trianglar matrix, then we would have a subalgebra" part

@GeoffRobinson Consider the algebra $\mathscr{A}$ generated by $\{A_i\}$, then the vector space $K^n$ is an $\mathscr{A}$ module. So if we have a nontrivila subalgebra of $\mathscr{A}$, then we would have a submodule of $K^n$, which is a common invariant subspace of $\{A_i\}$. If the matrix $(a_{ij})$ above is similar to a blocked upper trianglar matrix, then we would have a subalgebra. So the question reduces to(which is somehow my original question): if I have a $n\times n$ matrix over a UFD, and its determinant is reducible, is it similar to a blocked upper trianglar matrix?

@Geoff Robinson Thanks for comment! I read about the group determinant and I realize that the group determinant can be "defined" for any finite dimensional algebra(in my case I would consider the algebra generated by $A_i$) in the following way: find a linear basis $e_1, \cdots ,e_n$, form a matrix with entry $a_{ij}=e_ie_j$(and then express in terms of linear combination of $\{e_k\}$). If I regard $e_i$ as variables, then can the determinant of $(a_{ij})$ tell something?