I have attempted to solve this problem by eliminating the most common matches first and working my way down.
First, I set up the grid:
And labeled how many times am edge was used to create a 1×1 block.
And then added on top of that how many times the edges were used for 2×2 blocks.
And finally the big 4×4 square.
Then I removed the most commonly used edge; which was a tie upon many, so I chose at random.
And after removing the edge, I adjusted all the other numbers accordingly.
And chose a new most commonly used edge:
Removed it, and adjusted the numbers…
Repeat a few times…
Look at all these zeroes! We’re getting close…
Gee… this is a bit tedious, let’s do the last three all at once.
That’s a total of 10 matchsticks removed.
There are no 1×1, 2×2, 3×3, or 4×4 squares remaining.
In general: for a nxn board, one will need to remove (1/2)(n)(n+1) matchsticks.