For any matrix $A\in M_n(\mathbb{Q})$, we consider THE decomposition $A=PLU$ (given, for example by the Maple command LUDecomposition(.); that is, we fix the algorithm of decomposition).

Here $A$ is sparse (here we assume that $A$ has $n$ non-zero entries) and generic -for example, randomly choose $A$-. Let $z(n)$ the total number of non-zero entries $l_{i,j},i\not= j$ or $u_{i,j}$.

- Experiments show that $E(z(10))\approx 10.8$ and $E(z(100))\approx 115.2$. In particular, $L,U$ are sparse.

Note that always $z(n)\geq n$ because $A$ depends on $n$ independent parameters and, from $P$ (which is in a finite set) and $L,U$ we can recover $A$; in the same way, $P$ is never $I_n$.

- Now we assume that the non-zero entries of $A$ respect a given pattern, that is, we fix the list $\mathcal{L}=\{[i_1,j_1],\cdots,[i_k,j_k]\}$ of the indices of non-zero entries of $A$. Then, there is an associated pattern for $P,L,U$: if we do a generic choice of the parameters of $A$ in the fixed pattern, then $P$ is fixed and the non-zero entries of $=L,U$ will always be the same. Indeed, the patterns of $P,L,U$ can only change if some algebraic expressions are zero, which is impossible in the generic case.

Here are 2 extreme examples of patterns for $n = 10$.

where $z(A_1)=10$.

where $z(A_2)=15$.

To obtain the associated pattern of $P,L,U$, it suffices to test some random matrix $A$ respecting $\mathcal{L}$.

$\textbf{Conclusion.}$ 1. If $A$ respects a pattern, then $P,L,U$ respects some known pattern; it remains to study what can be practically done with it.

- Of course, all this requires an infinite field $K$; or if we are satisfied with a large probability, then $ K $ may be a large finite field. Similarly, if the $ a_ {i, j} $ are bounded integers, then the bound must be large.

$\textbf{Answer to the OP.}$ Let $m(A),z(A)$ be the number of non-zero entries of $A$ and $L,U$ and let $n=100$.

If $m(A)=100$, then $E(z)\approx 115.2$ -an increase of 15%- with a maximum of $\approx 143$.

If $m(A)=200$, then $E(z)\approx 350$ -an increase of 75%- with a maximum of $\approx 446$ (less than 5% of the available $L,U$ entries).

You must choose $m(A) = 510$ to fill (on average) the third of the available $L,U$ entries.

Thus if, for example, $m(A)\leq 200$, $L,U$ are sparse and $P,L,U$ generically respect some pattern associated with that of $A$.

Now, if $A\in M_{100}$ is always sparse symmetric and respects a pattern with $m(A)\leq 200$, then some experiments seem to show that, generically, $L,U$ are sparse an $P,L,U$ respect some associated pattern.