We investigate the stability properties of flows over an open square cavity for fluids with shear-dependent viscosity. The analysis is carried out in the context of linear theory using a normal-mode decomposition. The incompressible Cauchy equations, with a Carreau viscosity model, are discretized with a finite-element method. The characteristics of direct and adjoint eigenmodes are analyzed and discussed in order to understand the receptivity features of the flow. Furthermore, we identify the regions of the flow more sensitive to a spatially localized feedbacks by building a spatial map obtained from the product between the direct and the adjoint eigenfunctions. The analysis shows that the first global linear instability of the steady flow is a steady or unsteady three-dimensional bifurcation depending on the value of the power-law index n. The instability mechanism is always located inside the cavity and the linear stability results suggest a strong connection with the classical lid-driven cavity problem.