# What exacty is “matrix sparsity” $s$?

In many sources (like on Page 30 here), I found that the complexity of the original Harrow Hassidim Lloyd is stated as $\mathcal{O}(\log (N) s^2 \kappa^2/\epsilon)$ where $s$ is said to be the "matrix sparsity". What is a precise definition of the term "matrix sparsity"? I couldn't find it stated anywhere.

You have the definitions in your paper you link page 12. Simply said, it is a matrix with many 0s.
As an example take N = 16, and the polynomial function is just a simple function like 1.5*X, then your matrix has at most 1.5*log(16,2)=6 non-zero entries per row.

If you prefer a visual, you have it here:

I believe the way they use it is as

The maximum number of non-zero elements in any row.

Although that’s different to the way Wikipedia defines sparsity, which is essentially the average:

the total number of non-zero elements divided by the number of elements.