Algorithmic Solution for Systems of Linear Equations, in $\mathcal{O}(mn)$ time

The solution of a linear system appears in the vast majority of Linear Algebra operations [1], as well as related numerical methods, in statistical modelling, machine learning algorithms, numerical solution of differential equations, etc. These algorithms are essential for applications in almost any discipline involving computations, such as Engineering, Physics, Data Science, Finance, etc., among others [2]. The history of attempts to solve a Linear System is long, comprising the well-known Gaussian Elimination Algorithm for square systems [3,4]. A variety of types occur when formulating a linear system, such as systems with equal number of equations and unknowns (formulated with square input matrices), or systems with a few coefficients compared to the number of Equations (so called tall or underdetermined systems [5-7]), where an exact solution does not occur and we try to identify the best possible solution in terms of residual errors, as well as wide (or overdetermined) systems [8-10], with more coefficients than equations, which have infinite solutions, and we try to identify one. These both are non-square systems. Accordingly, the input matrix can be dense [11,12], with all the elements non zeros, or sparse [13, 14], with a few non zeros elements.