Centro de Informática · UFPE Álgebra Vetorial e LinearCIN0138 · 2026.2
Google Classroom

Aula 9 · 06/10 (ter) · Módulo 2 · laboratório

Os quatro subespaços fundamentais

Nesta aula você estuda os quatro subespaços fundamentais de uma matriz A de tamanho m × n e posto r. O espaço das linhas C(AT), de dimensão r, e o espaço nulo N(A), de dimensão n − r, são subespaços de ℝn. O espaço das colunas C(A), de dimensão r, e o espaço nulo à esquerda N(AT), de dimensão m − r, são subespaços de ℝm. Na bancada, você confere essas dimensões, escreve cada vetor x ∈ ℝn como a soma de um vetor do espaço das linhas com um vetor do espaço nulo e usa o espaço nulo à esquerda para decidir se o sistema Ax = b, com b ∈ ℝm, tem solução. Na parte Em dimensão n, mais abaixo, esses subespaços aparecem na matriz de incidência de um grafo.

Os quatro subespaços

Domínio

Contradomínio

Exemplos

Matriz A

As entradas podem ser inteiros, frações como 3/2 ou decimais como 0,5. A matriz pode ter de 2 a 3 linhas e de 2 a 4 colunas.

Vetor x no domínio

O vetor x se escreve, de um único modo, como x = xr + xn, com xr no espaço das linhas e xn no espaço nulo. Os botões abaixo trocam x por uma dessas duas partes.

Vetor b no contradomínio

O botão b = Ax, abaixo, troca b pelo vetor Ax, que pertence ao espaço das colunas. O botão Projetar b sobre C(A) troca b pela sua projeção ortogonal sobre o espaço das colunas C(A), que é o vetor de C(A) mais próximo de b. Projeções são estudadas na Aula 12.

O que mostrar

Pelo teclado: clique numa figura e use as setas; a barra de espaço alterna a ponta que se move. Sem ponta escolhida, as setas giram a figura.

Em dimensão n

Grafos: vértices, arestas e ciclos

Nesta parte, um grafo tem n vértices e m arestas. Cada aresta liga dois vértices distintos, dois vértices são ligados por no máximo uma aresta, e cada aresta recebe uma orientação, indicada por uma seta. A matriz de incidência do grafo é a matriz A de tamanho m × n com uma linha por aresta e uma coluna por vértice. Na linha de cada aresta, há −1 na coluna do vértice de onde ela sai, +1 na coluna do vértice aonde ela chega e 0 nas demais colunas. O grafo é conexo quando quaisquer dois vértices são ligados por um caminho, isto é, por uma sequência de vértices em que cada um é ligado ao seguinte por uma aresta, qualquer que seja a orientação dela. Num grafo conexo, o espaço nulo N(A) é formado pelos vetores constantes, que têm todas as coordenadas iguais, e o posto é r = n − 1. O espaço nulo à esquerda N(AT) é gerado pelos vetores dos ciclos do grafo, e por isso o número de ciclos independentes é m − r = m − n + 1. A guia Matriz de incidência, nos conceitos da aula, define os ciclos, os vetores dos ciclos, o número de ciclos independentes e as componentes conexas e demonstra esses fatos.

O grafo

Cada aresta tem uma seta que indica a orientação. Vértices da mesma componente conexa têm a mesma cor, e o ciclo escolhido aparece em âmbar.

A matriz de incidência A

Ferramenta

  • Com a ferramenta Criar e ligar, clique (ou toque) num espaço vazio do quadro O grafo para criar um vértice.
  • Clique num vértice para escolhê-lo: ele fica cercado por um círculo vermelho tracejado. Depois, clique em outro vértice para ligar os dois por uma aresta, orientada do primeiro para o segundo.
  • Com um vértice escolhido, um clique num espaço vazio cria um vértice novo já ligado a ele. Clique de novo no vértice escolhido para desfazer a escolha.
  • Com a ferramenta Apagar, clique num vértice, que é apagado com as arestas incidentes a ele, ou numa aresta.

Grafos prontos

Ciclos (espaço nulo à esquerda)

Os ciclos listados são os ciclos fundamentais de uma árvore geradora de cada componente conexa, definidos na guia Matriz de incidência: para cada aresta fora da árvore, o ciclo formado por essa aresta e pelo caminho da árvore que liga as suas pontas. Cada ciclo é percorrido no sentido da seta da sua aresta fora da árvore. Os vetores desses ciclos formam uma base do espaço nulo à esquerda N(AT).

Edição pelo teclado

Matrizes sorteadas com posto escolhido

Para toda matriz A de tamanho m × n e posto r, as dimensões dos dois subespaços contidos em ℝn somam r + (n − r) = n, e as dos dois subespaços contidos em ℝm somam r + (m − r) = m. O quadro As dimensões mostra essas duas somas como barras divididas. O quadro Produtos internos entre as bases usa uma lista de vetores: primeiro os vetores de uma base do espaço das linhas, depois os de uma base do espaço nulo. Com a opção Em ℝm do controle Bases mostradas, a lista tem primeiro uma base do espaço das colunas e depois uma base do espaço nulo à esquerda. A entrada (i, j) do quadro é o produto interno do vetor i com o vetor j da lista. Quando as duas bases têm vetores, duas linhas grossas separam as duas bases e dividem o quadro em quatro blocos. Os dois blocos fora da diagonal contêm os produtos internos entre um vetor de uma base e um vetor da outra. Eles são nulos, e por isso aparecem em branco: cada vetor de um dos subespaços é perpendicular a cada vetor do outro.

As dimensões

Produtos internos entre as bases

Matriz sorteada

Conceitos da aula

Os quatro subespaços fundamentais

Uma guia por conceito, cada um com a definição, um exemplo resolvido e o lugar da bancada em que ele aparece. A notação é a do livro-texto (seção 2.4).

Multiplicar por uma matriz A de tamanho m × n leva cada vetor x ∈ ℝn num vetor Ax ∈ ℝm; por isso chamamos ℝn de domínio e ℝm de contradomínio. Cada um desses dois espaços contém dois dos quatro subespaços fundamentais de A.

Os quatro subespaços fundamentais

Definição

Seja A uma matriz m × n. Os quatro subespaços fundamentais de A são:

  1. o espaço das colunas C(A) = {Ax : x ∈ ℝn}, o conjunto de todas as combinações lineares das colunas de A, contido em ℝm;
  2. o espaço nulo N(A) = {x ∈ ℝn : Ax = 0}, contido em ℝn;
  3. o espaço das linhas C(AT) = {ATy : y ∈ ℝm}, o conjunto de todas as combinações lineares das linhas de A, contido em ℝn;
  4. o espaço nulo à esquerda N(AT) = {y ∈ ℝm : ATy = 0}, contido em ℝm.

Os itens 3 e 4 usam a transposta AT, de tamanho n × m. A linha i de A, escrita como coluna, é a coluna i de AT, um vetor de ℝn. Assim, C(AT) e N(AT) são o espaço das colunas e o espaço nulo da matriz AT, e os quatro conjuntos são subespaços pelo que foi visto na Aula 6.

O nome “espaço nulo à esquerda” vem da transposição: ATy = 0 equivale a yTA = 0T, e nessa forma o vetor yT multiplica A pela esquerda. O produto yTA é a combinação linear das linhas de A cujos coeficientes são as coordenadas de y, na ordem. Assim, as coordenadas de cada y ∈ N(AT) são os coeficientes de uma combinação linear das linhas de A igual à linha nula.

Um exemplo em ℝ3

Exemplo

Na matriz A = 120011131, a terceira linha é a soma das duas primeiras. A forma escalonada reduzida de A é R = 10−2011000, com pivôs nas colunas 1 e 2. Então:

  • C(A) é gerado pelas colunas pivô (1, 0, 1)T e (2, 1, 3)T, pois a terceira coluna é −2(1, 0, 1)T + (2, 1, 3)T. Como esses dois vetores não são múltiplos um do outro, C(A) é um plano que passa pela origem de ℝ3.
  • Ax = 0 tem as mesmas soluções que Rx = 0, que dá x1 = 2x3 e x2 = −x3. Logo N(A) = {λ(2, −1, 1)T : λ ∈ ℝ}, uma reta que passa pela origem.
  • C(AT) é gerado pelas linhas de A. Como as operações elementares sobre linhas não mudam esse subespaço, ele também é gerado pelas linhas não nulas de R, (1, 0, −2)T e (0, 1, 1)T: é outro plano que passa pela origem.
  • N(AT) é o conjunto das soluções de ATy = 0. A forma escalonada reduzida de AT tem as linhas não nulas (1, 0, 1) e (0, 1, 1), e a única variável livre é a terceira coordenada de y. A solução especial é (−1, −1, 1)T, logo N(AT) = {λ(1, 1, −1)T : λ ∈ ℝ}, outra reta que passa pela origem. De fato, com os coeficientes 1, 1 e −1, a combinação linear das linhas de A é nula: linha 1 + linha 2 − linha 3 = 0T.

Na bancada: no painel Exemplos, escolha Sensor redundante. As quatro caixas logo abaixo da figura do quadro Os quatro subespaços mostram as bases. O quadro Domínio desenha C(AT) em azul e N(A) em verde; o quadro Contradomínio desenha C(A) em roxo e N(AT) em âmbar.

Seja A uma matriz de tamanho m × n e posto r, o número de pivôs. As dimensões dos quatro subespaços fundamentais de A dependem só de m, n e r. As bases são obtidas da eliminação, que leva A à sua forma escalonada reduzida R.

As quatro dimensões

Teorema

(Teorema fundamental da Álgebra Linear, parte 1.) Seja A uma matriz m × n de posto r. Então

dim C(A) = dim C(AT) = r,

dim N(A) = n − r,

dim N(AT) = m − r.

Em particular, as dimensões dos dois subespaços contidos em ℝn somam r + (n − r) = n, e as dos dois subespaços contidos em ℝm somam r + (m − r) = m.

Por quê. Seja R a forma escalonada reduzida de A. Cada operação elementar sobre linhas equivale a multiplicar a matriz, pela esquerda, por uma matriz invertível. Chame de E o produto das matrizes das operações que levam A até R. Então E é invertível e EA = R. Na prática, E se obtém aplicando essas operações à matriz [A | I], que se transforma em [R | E]. Cada subespaço tem uma base com o número de vetores do teorema:

  • Espaço das linhas: as r linhas não nulas de R. As operações elementares substituem linhas por combinações lineares das linhas e podem ser desfeitas, logo não mudam o espaço das linhas. Essas r linhas são LI, pois cada uma tem um 1 numa coluna pivô em que as outras têm 0.
  • Espaço nulo: as n − r soluções especiais, uma para cada variável livre (Aula 8).
  • Espaço das colunas: as r colunas pivô de A, e não as de R. A combinação linear das colunas de A com coeficientes x1, …, xn é o vetor Ax. Como Ax = 0 e Rx = 0 têm as mesmas soluções, uma combinação linear das colunas de A é nula se, e somente se, a combinação com os mesmos coeficientes das colunas de R é nula. Em R, as colunas pivô são colunas distintas da matriz identidade, logo LI, e cada uma das outras colunas é combinação linear delas. Pela equivalência anterior, o mesmo vale para as colunas de A, com os mesmos coeficientes.
  • Espaço nulo à esquerda: as últimas m − r linhas de E, escritas como colunas. A linha i de R = EA é a linha i de E vezes A. As últimas m − r linhas de R são nulas, então cada uma das últimas m − r linhas de E, escrita como vetor y, satisfaz yTA = 0T. Essas linhas são LI, porque E é invertível. Falta ver que N(AT) tem dimensão m − r. Pelo primeiro item, aplicado a AT, o posto de AT é a dimensão do espaço gerado pelas linhas de AT, que são as colunas de A; pelo terceiro item, essa dimensão é r. Pelo segundo item, aplicado a AT, que tem m colunas, dim N(AT) = m − r. Logo essas m − r linhas formam uma base de N(AT) (Aula 7).

Um exemplo 3 × 4

Exemplo

A matriz do exemplo do livro-texto e a sua forma escalonada reduzida são

A = 13322697−1−334,

R = 130−100110000.

Os pivôs estão nas colunas 1 e 3; logo r = 2, e as variáveis livres são x2 e x4. As bases são:

  • espaço das linhas: (1, 3, 0, −1)T e (0, 0, 1, 1)T;
  • espaço nulo: (−3, 1, 0, 0)T e (1, 0, −1, 1)T;
  • espaço das colunas: (1, 2, −1)T e (3, 9, 3)T, a primeira e a terceira colunas de A;
  • espaço nulo à esquerda: (5, −2, 1)T, pois 5(linha 1) − 2(linha 2) + (linha 3) = 0T.

As dimensões são 2 e 2 em ℝ4, com 2 + 2 = 4, e 2 e 1 em ℝ3, com 2 + 1 = 3.

Na bancada: a missão 1 do roteiro carrega essa matriz com as dimensões escondidas; ela também está no painel Exemplos, como Exemplo do livro. No painel Matriz A, os botões de sorteio trocam A por outra matriz do mesmo tamanho com o posto escolhido, e as caixas logo abaixo da figura do quadro Os quatro subespaços dizem de onde vem cada base.

O espaço das linhas e o espaço nulo de uma matriz A de tamanho m × n são subespaços do domínio ℝn. Todo vetor de um deles é perpendicular a todo vetor do outro, e cada vetor x ∈ ℝn se escreve, de um único modo, como a soma de um vetor do espaço das linhas com um vetor do espaço nulo.

Espaço das linhas e espaço nulo

Lembre que dois vetores u, v ∈ ℝn são perpendiculares (ou ortogonais) quando o produto interno uTv = u1v1 + ⋯ + unvn é zero.

Propriedade

Seja A uma matriz m × n. Todo vetor de N(A) é perpendicular a todo vetor de C(AT).

Por quê. A coordenada i de Ax é o produto da linha i de A por x. Assim, Ax = 0 diz exatamente que x é perpendicular a cada linha de A e, então, também a toda combinação linear das linhas. Em fórmulas: todo vetor de C(AT) é da forma ATy, com y ∈ ℝm, e, se Ax = 0,

(ATy)Tx = yT(Ax) = yT0 = 0.

Na Aula 12 (seção 3.1 do livro-texto), dois subespaços com essa propriedade são chamados de subespaços ortogonais. A Aula 12 também mostra que cada um desses dois subespaços é o complemento ortogonal do outro: N(A) é formado por todos os vetores de ℝn perpendiculares a todos os vetores de C(AT), e vice-versa.

A decomposição x = xr + xn

Propriedade

Seja A uma matriz m × n. Para cada x ∈ ℝn, existem um único xr ∈ C(AT) e um único xn ∈ N(A) tais que

x = xr + xn.

Além disso, Ax = Axr.

O vetor xr se chama a parte de x no espaço das linhas, e xn, a parte de x no espaço nulo. Os índices seguem o livro-texto: r vem de row space (espaço das linhas, em inglês), e n vem de nullspace (espaço nulo). Eles são rótulos, escritos em letra reta: não são o posto r, nem o número n de colunas, nem índices de coordenadas.

Por quê. A demonstração tem quatro passos.

  1. Só o vetor nulo pertence aos dois subespaços. Se v pertence a C(AT) e a N(A), a propriedade anterior diz que v é perpendicular a si mesmo: vTv = v12 + ⋯ + vn2 = 0. Uma soma de quadrados só é nula quando todas as parcelas são nulas, logo v = 0.
  2. Duas bases juntas formam uma base de ℝn. Tome uma base de C(AT), com r vetores, e uma base de N(A), com n − r vetores (guia Dimensões e bases). Se uma combinação linear desses n vetores é o vetor nulo, a parte da combinação feita com a primeira base é igual a menos a parte feita com a segunda. Esse vetor pertence aos dois subespaços, logo é nulo pelo passo 1. Como cada base é LI, todos os coeficientes são nulos. Assim, os n vetores são LI e, por serem n vetores LI de ℝn, formam uma base de ℝn (Aula 7).
  3. Existência e unicidade. Escreva x nessa base. A soma dos termos com os vetores da base de C(AT) é xr, e a soma dos termos com os vetores da base de N(A) é xn. Se também x = x′r + x′n, com x′r ∈ C(AT) e x′n ∈ N(A), então o vetor xr − x′r = x′n − xn pertence aos dois subespaços e é nulo pelo passo 1.
  4. Por fim, Ax = Axr + Axn = Axr, pois Axn = 0.

Exemplo

Tome a matriz A do exemplo Sensor redundante, vista na guia Os quatro subespaços, e x = (3, 1, 1)T. A parte de x no espaço das linhas é xr = (1, 2, 0)T, que pertence a esse espaço porque (1, 2, 0)T = (1, 0, −2)T + 2(0, 1, 1)T. A parte no espaço nulo é xn = (2, −1, 1)T. De fato,

(3, 1, 1)T = (1, 2, 0)T + (2, −1, 1)T.

As duas partes são perpendiculares, pois xrTxn = 2 − 2 + 0 = 0, e

Ax = Axr = (5, 2, 7)T.

Para encontrar as duas partes de outro vetor x, procure os escalares λ1, λ2 e μ tais que x = λ1(1, 0, −2)T + λ2(0, 1, 1)T + μ(2, −1, 1)T. Esse sistema linear tem uma única solução, pois os três vetores formam uma base de ℝ3 (passo 2 da demonstração acima). Então xr = λ1(1, 0, −2)T + λ2(0, 1, 1)T e xn = μ(2, −1, 1)T. A Aula 12 mostra um caminho mais direto: xr é a projeção ortogonal de x sobre o espaço das linhas, e é assim que a bancada calcula xr.

Na bancada: no quadro Domínio, arraste a ponta preta de x, a azul de xr ou a verde de xn; a leitura abaixo da figura mostra as duas partes e o produto interno entre elas. No quadro Contradomínio, a seta de Ax não se move quando só xn muda. No painel Vetor x no domínio, os botões x = xr e x = xn trocam x por uma das suas partes.

O espaço das colunas e o espaço nulo à esquerda de uma matriz A de tamanho m × n são subespaços do contradomínio ℝm. Os vetores do espaço nulo à esquerda permitem decidir se o sistema Ax = b, com b ∈ ℝm, tem solução: basta calcular yTb para cada vetor y de uma base desse subespaço.

O teste yTb

Propriedade

Seja A uma matriz m × n. Todo vetor de N(AT) é perpendicular a todo vetor de C(A).

De fato, se ATy = 0, então, para todo x ∈ ℝn,

yT(Ax) = (ATy)Tx = 0Tx = 0.

É a propriedade da guia Espaço das linhas, aplicada à matriz AT no lugar de A.

Teorema

Seja A uma matriz m × n e seja b ∈ ℝm. O sistema Ax = b tem solução se, e somente se, yTb = 0 para todo y ∈ N(AT). Basta verificar essa condição para os vetores de uma base de N(AT).

Por quê. A demonstração tem três passos.

  1. Se Ax = b tem solução, então b = Ax para algum x ∈ ℝn, e a conta acima dá yTb = 0 para todo y ∈ N(AT).
  2. Reciprocamente, suponha que yTb = 0 para todo y ∈ N(AT). Seja R a forma escalonada reduzida de A, de posto r, e seja E a matriz invertível com EA = R, da guia Dimensões e bases. Multiplicando os dois lados por E, ou por E−1 na volta, vemos que Ax = b e Rx = Eb têm as mesmas soluções. As últimas m − r linhas de R são nulas, então Rx = Eb tem solução se, e somente se, as últimas m − r coordenadas de Eb são nulas (Aula 8). Para cada uma dessas coordenadas, escreva como coluna a linha correspondente de E e chame esse vetor de y. A coordenada é yTb, e y pertence a N(AT) pela guia Dimensões e bases. Logo essas coordenadas são nulas, e o sistema tem solução.
  3. Basta verificar a condição numa base. Se N(AT) = {0}, não há o que verificar. Senão, sejam y1, …, ym−r os vetores de uma base de N(AT), todos com produto interno nulo com b. Todo y ∈ N(AT) se escreve como y = λ1y1 + ⋯ + λm−rym−r, com escalares λ1, …, λm−r. Então yTb é a combinação linear dos produtos y1Tb, …, ym−rTb com os mesmos coeficientes, e vale 0.

Dois exemplos

Exemplo

No exemplo Sensor redundante, a coordenada i de Ax é a medida do sensor i, e o vetor b reúne as leituras dos três sensores. A terceira linha de A é a soma das duas primeiras, então o terceiro sensor mede a soma das medidas dos outros dois. O espaço nulo à esquerda é formado pelos múltiplos de y = (1, 1, −1)T. Para as leituras b = (3, 5, 9)T,

yTb = 3 + 5 − 9 = −1 ≠ 0,

logo Ax = b não tem solução: alguma leitura está errada. Com b = (3, 5, 8)T, temos yTb = 0, e o sistema tem solução; por exemplo, x = (−7, 5, 0)T.

Exemplo

No exemplo Reta por três medidas, as colunas de A são (1, 1, 1)T e (0, 1, 2)T, e as coordenadas de Ax são os valores x1 + x2t da reta de coeficientes x1 e x2 nos instantes t = 0, 1, 2. O espaço nulo à esquerda é gerado por y = (1, −2, 1)T. Para as medidas b = (1, 2, 4)T,

yTb = 1 − 4 + 4 = 1 ≠ 0:

nenhuma reta passa pelos três pontos (0, 1), (1, 2) e (2, 4), em que a primeira coordenada é o instante e a segunda, a medida. A Aula 12 encontra, pelo método dos mínimos quadrados, a reta que torna mínima a soma dos quadrados das diferenças entre as medidas e os valores da reta nos três instantes.

Na bancada: no quadro Contradomínio, arraste a ponta vermelha de b, ou use os controles do painel Vetor b no contradomínio, e acompanhe os valores de yTb na leitura abaixo da figura. As missões 5 e 6 do roteiro usam esse teste.

Na matriz de incidência de um grafo, os subespaços fundamentais descrevem a estrutura do grafo: a dimensão do espaço nulo é o número de componentes conexas, e o espaço nulo à esquerda é gerado pelos vetores dos ciclos.

A matriz de incidência

Definição

Seja G um grafo com vértices 1, …, n e arestas e1, …, em. Cada aresta liga dois vértices distintos, dois vértices são ligados por no máximo uma aresta, e cada aresta recebe uma orientação: ela sai de um dos seus vértices e chega ao outro. A matriz de incidência de G é a matriz A de tamanho m × n tal que, se a aresta ei sai do vértice j e chega ao vértice k, então aij = −1, aik = +1 e as demais entradas da linha i são nulas.

Seguimos a convenção do livro-texto, com uma linha por aresta; muitos textos de teoria dos grafos usam a transposta dessa matriz. Um vetor x ∈ ℝn associa a cada vértice j a coordenada xj, que chamamos de potencial do vértice. Se a aresta ei sai do vértice j e chega ao vértice k, a coordenada i de Ax é xk − xj, a diferença de potencial ao longo da aresta. Do mesmo modo, um vetor y ∈ ℝm associa a cada aresta ei a sua coordenada i, que chamamos de fluxo na aresta, positivo no sentido da seta. A coordenada j de ATy é o fluxo total que chega ao vértice j menos o fluxo total que sai dele.

Um caminho é uma sequência de vértices em que cada vértice é ligado ao seguinte por uma aresta, qualquer que seja a orientação dela. O grafo G é conexo quando dois vértices quaisquer são ligados por um caminho. A componente conexa de um vértice é o conjunto formado por ele e pelos vértices ligados a ele por caminhos. Cada vértice pertence a exatamente uma componente conexa.

Um ciclo de G é formado por pelo menos três vértices distintos, percorridos em sequência, e pelas arestas que ligam cada um deles ao seguinte e o último ao primeiro. O ciclo não depende do vértice de partida nem do sentido em que é percorrido. Escolhido um dos dois sentidos de percurso, o vetor do ciclo é o vetor de ℝm cuja coordenada i é +1 se a aresta ei é percorrida no sentido da sua seta, −1 se ela é percorrida no sentido contrário e 0 se ela não pertence ao ciclo. O outro sentido de percurso dá o vetor oposto. Alguns ciclos são independentes quando os seus vetores são LI. O número de ciclos independentes de G é a maior quantidade de ciclos independentes que se pode escolher em G.

Espaço nulo e ciclos

Teorema

Seja A a matriz de incidência de um grafo conexo com n vértices e m arestas. Então:

  1. N(A) = {λ(1, 1, …, 1)T : λ ∈ ℝ}, o conjunto dos vetores constantes; logo o posto de A é r = n − 1;
  2. os vetores dos ciclos pertencem a N(AT) e geram N(AT), cuja dimensão é m − r = m − n + 1; logo o número de ciclos independentes é m − n + 1.

Por quê. (1) Pela fórmula da coordenada i de Ax, a equação Ax = 0 diz que as duas pontas de cada aresta têm o mesmo potencial. Num grafo conexo, dois vértices quaisquer são ligados por um caminho, e o potencial não muda ao longo dele; logo x é constante. Reciprocamente, todo vetor constante satisfaz Ax = 0. Então dim N(A) = 1, e o posto é r = n − dim N(A) = n − 1.

(2) Primeiro, o vetor y de um ciclo pertence a N(AT). Pela fórmula acima, a coordenada j de ATy soma as coordenadas de y nas arestas que chegam ao vértice j e subtrai as coordenadas de y nas arestas que saem dele. Se o vértice j não está no ciclo, nenhuma aresta do ciclo toca j, e essa coordenada é 0. Se j está no ciclo, o percurso chega a j por uma aresta e sai por outra. A aresta de chegada contribui com +1: se a sua seta aponta para j, ela é percorrida no sentido da seta e a sua coordenada +1 é somada; se a sua seta sai de j, ela é percorrida no sentido contrário e a sua coordenada −1 é subtraída. Do mesmo modo, a aresta de saída contribui com −1. Logo ATy = 0.

Depois, os ciclos geram N(AT). Uma árvore geradora de G é um conjunto de arestas de G que liga todos os n vértices e não contém ciclo. Ela pode ser obtida a partir de um vértice qualquer, acrescentando um vértice de cada vez, ligado por uma aresta de G a um vértice já alcançado; assim, ela tem n − 1 arestas. Cada uma das m − n + 1 arestas fora da árvore forma, com o caminho da árvore que liga as suas pontas, um ciclo, chamado ciclo fundamental. Os vetores dos ciclos fundamentais são LI, pois cada um tem coordenada não nula numa aresta fora da árvore em que os outros têm coordenada nula. São m − n + 1 = dim N(AT) vetores LI de N(AT), logo formam uma base (Aula 7).

Se o grafo tiver várias componentes conexas, o mesmo argumento, aplicado a cada componente, mostra que N(A) é formado pelos vetores constantes em cada componente. A dimensão de N(A) é o número de componentes, e o posto é n menos esse número. Os vetores dos ciclos continuam gerando N(AT): basta tomar uma árvore geradora de cada componente.

Suponha agora que o grafo seja conexo e esteja desenhado no plano sem cruzamentos de arestas. Chame de f o número de regiões em que o desenho divide o plano, contando a região ilimitada. A fórmula de Euler diz que n − m + f = 2. Então o número de regiões limitadas, f − 1, é igual a m − n + 1, o número de ciclos independentes.

Exemplo

No grafo Quadrado com uma diagonal, as arestas são e1: 1 → 2, e2: 2 → 3, e3: 3 → 4, e4: 4 → 1 e e5: 1 → 3, e a matriz de incidência é

A = −11000−11000−11100−1−1010.

O grafo é conexo, então N(A) é gerado por (1, 1, 1, 1)T, o posto é r = 3 e dim N(AT) = 5 − 3 = 2. O grafo tem três ciclos: os triângulos 1 → 2 → 3 → 1 e 1 → 3 → 4 → 1 e o quadrado 1 → 2 → 3 → 4 → 1. Os vetores dos dois triângulos, percorridos nesses sentidos, são

y1 = (1, 1, 0, 0, −1)T,

y2 = (0, 0, 1, 1, 1)T,

e o vetor do quadrado, percorrido nesse sentido, é y1 + y2 = (1, 1, 1, 1, 0)T. Há três ciclos, mas o número de ciclos independentes é 2, como prevê a conta m − n + 1 = 5 − 4 + 1 = 2.

Na bancada: na parte Em dimensão n, escolha Quadrado com uma diagonal no painel Grafos prontos. No painel Ciclos (espaço nulo à esquerda), o controle Ciclo escolhe o ciclo 1 ou o ciclo 2, e a leitura abaixo dele mostra os vetores y1 e y2 deste exemplo. O quadro A matriz de incidência A contorna as linhas das arestas do ciclo escolhido. Os blocos abaixo da figura do quadro O grafo mostram o posto, a dimensão de N(A) e o número de ciclos independentes.

Para pensar

Uma matriz 3 × 3 pode ter o espaço das colunas igual ao espaço nulo?

Não. Seja A uma matriz 3 × 3 de posto r. O espaço das colunas C(A) tem dimensão r, e o espaço nulo N(A) tem dimensão 3 − r. Se C(A) = N(A), as duas dimensões são iguais, isto é, r = 3 − r, e nenhum inteiro r satisfaz essa igualdade.

Em geral, para uma matriz n × n de posto r, a igualdade exige r = n − r, isto é, n = 2r, e então n é par. Para matrizes 2 × 2, pode acontecer: com A = 0100, temos Ax = (x2, 0)T para todo x = (x1, x2)T. Logo C(A) e N(A) são, ambos, a reta formada pelos múltiplos de (1, 0)T.

Num grafo conexo com 10 vértices e 15 arestas, qual é o número de ciclos independentes?

Seis. Seja A a matriz de incidência do grafo, com n = 10 vértices e m = 15 arestas. Como o grafo é conexo, o espaço nulo N(A) é formado pelos vetores constantes, e o posto é r = n − 1 = 9. Logo dim N(AT) = m − r = 15 − 9 = 6, que é m − n + 1 = 15 − 10 + 1. A conta não depende de o grafo poder ser desenhado no plano sem cruzamentos de arestas. O grafo de Petersen, por exemplo, tem 10 vértices e 15 arestas, não é planar, isto é, não admite um desenho desses, e o seu número de ciclos independentes é 6.

Se Ax = b tem solução, quantas soluções pertencem ao espaço das linhas?

Exatamente uma. Para ver que existe uma, tome uma solução x e a sua parte xr no espaço das linhas, definida na guia Espaço das linhas. Como Axr = Ax = b, o vetor xr é uma solução que pertence ao espaço das linhas.

Para ver que ela é única, suponha que duas soluções s e s′ pertencem ao espaço das linhas. A diferença s − s′ também pertence a ele e, como A(s − s′) = b − b = 0, pertence ao espaço nulo. Só o vetor nulo pertence aos dois subespaços, logo s = s′.

Essa solução é a de menor comprimento. Duas soluções diferem por um vetor de N(A), e então, pela unicidade da decomposição, todas têm a mesma parte xr. Como xrTxn = 0, cada solução x = xr + xn satisfaz ‖x‖2 = ‖xr‖2 + ‖xn‖2 ≥ ‖xr‖2, com igualdade só quando xn = 0.