Marek080 has the right idea. You say you're going to precompute the array in the setup loop. You could just precompute it outside the Arduino program entirely, and store the data in Flash.
You also said 5 states will take 2.5K, which makes me think you're storing each LED state as a byte. As he points out if you're just storing on/off then each matrix entry will only take 64 bytes.
Another option would be to add an SD card -- with that you could either precompute the matrices on a bigger computer, copy them to the card, and stick it in the Arduino, or you could do as you originally suggested and do all the computation in the setup loop, but instead of storing the states in RAM save them to the SD card.
Good luck!