Muito boa a pergunta!!!
Para entender o que está acontecendo, precisamos antes entender como funciona a estrutura de memória de um programa em C.
Basicamente, o programa está dividido em 5 regiões de memória, que são:
1. Segmento de texto (Text Segment)
Nesta parte fica o código de fato do programa, isto é, as intruções de máquina geradas pelo compilador.
2. Segmento de dados inicializados (Initialized Data Segment)
Contém as variáveis globais (isto é, declaradas fora do escopo de alguma função) e as variáveis "static" (que foram delcaradas com o comando static) que forem inicializadas pelo programador.
3. Segmento de dados não-inicializados (Uninitialized Data Segment / bss)
Região análoga à região 2, porém aqui ficam as variáveis que não foram inicializadas pelo programador.
4. Pilha de execução (Stack)
Aqui a coisa começa a ficar mais séria, esta região guarda a pilha de execução do programa, isto é, para cada função que está sendo executada, guarda-se o estado das variáveis locais dela.
5. Heap
Esta é a maior região de memória. Toda memória alocada dinâmicamente vai para esta região.
Em tese, esta região pode ocupar toda a memória física do computador.
Ufa, ficou um pouco longo, mas agora, consigo responder as suas perguntas:
Quando você declarou a matriz sem o "static" dentro do main, essa memória foi alocada como uma variável local da função main, portanto foi parar na região 4 (pilha de execução), como era uma matriz muito grande, ela estourou a pilha (sim, a pilha tem um tamanho limitado).
Quando acontece este fenômeno ele é chamado de "Stack Overflow"
Quando você declarou ela como "static", ela foi parar na região 2 ou 3, que são maiores, porém se você tentar aumentar mais, vai continuar encontrando problemas.
No meu teste aqui, meu programa imprimiu "killed" e não uma SegFault.
Já a sua outra pergunta, a memória alocada na inicialização do programa é a que pertece às regiões 1, 2 e 3. As que vão ficar nas regiões 4 e 5 são alocadas apenas quando forem exigidas, digamos assim. Vai ser fácil ver a região 5 em ação quando vocês começarem a alocar memória dinâmicamente.
Se alguma coisa não ficou clara ou gerou alguma outra dúvida, pode perguntar!