Why is $8 \times 8$ matrix chosen for Discrete Cosine Transform? In JPEG and MPEG, why is $8 \times 8$ matrix chosen for Discrete Cosine Transform?
Why not any other, say $64 \times 64$?
 A: The DCT treats the block as if it were periodic and has to reconstruct the resulting jump at the boundaries. If you take 64x64 blocks, you'll most likely have a huge jump at the boundaries, and you'll need lots of high-frequency components to reconstruct that to a satisfactory precision. The $8$ results from a tradeoff that can't be theoretically optimized, but seems to work well for typical images, where the variation across 8x8 blocks is typically small enough that blocking artifacts can be avoided without having to encode too much high-frequency information.
Also $8$ is a power of $2$, so even if the optimal tradeoff from the information-content point of view had been, say, 10, one might still have chosen $8$ because the transform is much simpler and quicker to perform.
Edit in response to the comment: Compression is always a tradeoff. You can always get sharper images by keeping more of the information -- you can get sharp images with 4x4, 8x8 or 64x64 blocks simply by keeping the entire high-frequency information. The question is how to reduce the amount of information as much as possible with as little visible difference as possible. Experience shows that in 8x8 blocks you can drop a lot of the information without creating unacceptable blocking artifacts. Certainly for 4x4 blocks the boundary jump would be even less, but there would also be less opportunity for compression. Consider an 8x8 block made up of four 4x4 blocks: If you transform each of the 4x4 blocks separately, you have to store their averages (zero-frequency components) with the same (high) precision for all four of them. If you transform them together as an 8x8 block, instead of those four averages, you get one average and three oscillating components that you can store with lower precision. All this can't be put into a single precise formula; one has to look at how data in real-world images are actually distributed and then make the required tradeoffs.
A: From the MPEG FAQ:

Q22. Why was the 8x8 DCT size chosen?
A Experiments showed little compaction gains could be acheived with
  larger 
      sizes, especially when considering the increased implementation
      complexity. A fast DCT algorithm will require roughly double the
      arithmetic operations per sample when the linear transform point
      size is doubled. Naturally, the best compaction efficiency has
  been
      demonstrated using locally adaptive block sizes (e.g. 16x16, 16x8,
      8x8, 8x4, and 4x4) (See Gary Sullivan and Rich Baker 'Efficient Quadtree
      Coding of Images and Video,' ICASSP 91, pp 2661-2664.). 
      Inevitably, this introduces additional side information overhead and 
      forces the decoder to implement programmable or hardwired
  recursive 
      DCT algorithms. If the DCT size becomes too large, then more edges
      (local discontinuities) and the like become absorbed into the
      transform block, resulting in wider propagation of Gibbs (ringing)
  and
      other phenomena.  Finally, with larger transform sizes, the DC
  term is
      even more critically sensitive to quantization noise.

