What is the computational complexity of $Ax = b$ and $AX = B$?

Question

Suppose $A, A_i$ are $m\times m$-matrices, $x_i, b_i$ are $m \times 1$, $X$ and $B$ are $m \times n$-matrices.

What is the total computational burden of solving $A_ix_i = b_i$ for $i = 1, 2, \dots, n$ versus $AX = B$ (where we might assume $A_1 =A_2 = \dots A_n = A$).

Answer 1

This is the general question of linear programming, and there are a number of works on the question. In short, linear programming is in P.

This is an older paper surveying some results: Megiddo, Nimrod. On the complexity of linear programming. IBM Thomas J. Watson Research Division, 1986. https://theory.stanford.edu/~megiddo/pdf/wcongres_4.0.a.pdf