 Solution

Solving the $m$ unrelated shifted systems by separate Gaussian elimination costs $\boxed{\frac{2}{3}{m}^4+O(m^3)}$ floating-point operations.

Instead compute $H=Q^{T}AQ$ once in $O(m^3)$ work. For each shift, solveThe shift changes only the diagonal, so $H-{\lambda }_{j}I$ remains an upper Hessenberg matrix. In each elimination column only the entry immediately below the pivot needs removal. With partial pivoting the only possible nonzero candidate rows are the current row and the next, and each update touches $O(m)$ entries. Factorization therefore costs $O(m^2)$ per shift; the triangular solve and both orthogonal-vector transformations also cost $O(m^2)$ each.

Thus $m$ shifted solves plus the initial Hessenberg reduction cost $\boxed{O(m^3)}$ in total. Pivoting is still needed in general: nonsingularity excludes a singular system but does not by itself guarantee that every unpivoted elimination pivot is nonzero.