Start with a linear system of the form \begin{equation*} Ax + Bt + C = 0, \end{equation*} where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of parameters, $A \in GL(n, \mathbb R)$, $B \in \mathcal M_{n,m}(\mathbb R)$ and $C \in \mathbb R^n$. Suppose you can apply Gauss reduction without pivoting. Then you end up with a system of the form \begin{equation*} Ux + Pt + Q = 0, \end{equation*} where $U$ is a $n \times n$ unitriangular matrix, $P \in \mathcal M_{n,m}(\mathbb R)$ and $Q \in \mathbb R^n$. This allows to compute $x$ recursively by: \begin{equation} \begin{cases} x_n = -(p_{n1} t_1 + \dots + p_{nm} t_m + q_n) \\ x_{n-1} = -(u_{n-1,n} x_n + p_{n-1,1} t_1 + \dots + p_{n-1,m} t_m + q_{n-1}) \\ \dots \\ x_1 = -(u_{12} x_2 + \dots + u_{1n} x_n + p_{11} t_1 + \dots + p_{1m} t_m + q_1) \\ \end{cases} \end{equation}

Of course, you can do this for every permutation of $(x_1, \dots, x_n)$, and also for every permutation of rows that does not give you zeroes on the diagonal at some point of Gauss reduction. Now my questions are:

Is it possible to know in advance (i.e. without doing the whole computation) which permutation of rows does not make Gauss reduction fail because of zeroes on the diagonal? I think this is very classical but I did not find any reference.

Is it possible to know in advance which permutation of rows and columns gives you the triple $(U, P, Q)$ with the greatest number of zeroes? This would give me the best algorithm that computes $x$ from a given $t$.

Does it help if you make some assumptions on the form of $A$? In my situation $A$ is sparse, often it is also symmetric and weakly diagonally dominant.

Thank you in advance.

solvingfor $t$ (in which case it seems that it's really part of the vector of variables) or regarding $t$ as fixed (in which case it seems that $B t + C$ is just a complicated way of naming the inhomogeneity)? It seems like you're asking for a quick way to determine to which Bruhat coset $B w B$ the matrix $A$ belongs, but I'm not sure. $\endgroup$ – LSpice Apr 13 at 22:011more comment