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

Aula 8 · 29/09 (ter) · Módulo 2 · laboratório

Resolução de Ax = 0 e Ax = b

Nesta aula você resolve os sistemas Ax = 0 e Ax = b levando a matriz A à forma escalonada reduzida, que se escreve R. As incógnitas das colunas de R sem pivô são as variáveis livres, e a cada uma delas corresponde uma solução especial. Se A tem n colunas e posto r, isto é, se R tem r pivôs, as n − r soluções especiais formam uma base do espaço nulo de A. Na bancada, você reduz a matriz aumentada [A | b] passo a passo e monta a solução completa, que é uma solução particular somada a um vetor do espaço nulo. Os exemplos incluem uma rede de pacotes e sistemas com três incógnitas, em que cada equação descreve um plano do espaço euclidiano E3, formado por pontos, enquanto o conjunto das soluções e o espaço nulo são formados por vetores de ℝ3.

A rede de pacotes

O vetor x em barras

Cada barra é uma coordenada do vetor x. As barras coloridas são as variáveis livres: arraste uma delas para mudar o seu valor. As barras pretas são as variáveis pivô, que a bancada calcula a partir das variáveis livres pelas linhas da forma escalonada reduzida, mostrada no quadro Eliminação até R. Quando o sistema tem solução, x é uma solução, e o contorno tracejado mostra a solução particular xp, a que tem as variáveis livres iguais a 0. Quando o sistema não tem solução, x é um vetor do espaço nulo N(A).

Solução completa

Eliminação até R

A eliminação aplica à matriz aumentada [A | b], um passo por vez, as operações elementares sobre linhas que levam A à sua forma escalonada reduzida R. A última coluna, que era b, passa a ser um vetor que se escreve d, e a matriz final é [R | d]. Abaixo da matriz, as incógnitas aparecem marcadas como variáveis pivô ou variáveis livres à medida que a eliminação avança. No último passo, todas estão marcadas.

Exemplos

Sistema [A | b]

As entradas podem ser inteiros, frações como 3/2 ou decimais como 0,5. A última coluna é o lado direito b. Com os botões − e +, o sistema pode ter de 1 a 4 equações e de 2 a 6 incógnitas.

Teste um vetor v

Digite as coordenadas de v: a conta de Av aparece linha por linha, e a leitura diz se v pertence a N(A) ou é solução de Ax = b.

O que mostrar

Pelo teclado: clique no quadro O vetor x em barras. As setas para a esquerda e para a direita escolhem a variável livre, e as setas para cima e para baixo mudam o valor dela.

Em dimensão n

A dimensão do espaço nulo

Seja A uma matriz de m linhas e n colunas, com posto r. Então A tem n − r variáveis livres e o mesmo número de soluções especiais, qualquer que seja m. Como as soluções especiais formam uma base do espaço nulo, dim N(A) = n − r. Nesta parte, você sorteia matrizes de até 12 linhas e 12 colunas e vê a forma escalonada reduzida R e as soluções especiais. Mais abaixo, um bloco de imagem de p linhas e q colunas, do qual só se conhecem as somas das linhas e das colunas, leva a um sistema linear cujo espaço nulo tem dimensão (p − 1)(q − 1).

A forma escalonada reduzida R

As soluções especiais

A matriz A

Solução especial

A cada variável livre corresponde uma solução especial: a solução de Ax = 0 em que essa variável vale 1 e as outras variáveis livres valem 0. As variáveis pivô dela são obtidas das linhas de Rx = 0. As soluções especiais seguem a ordem das variáveis livres: a primeira se escreve s1, a segunda, s2, e assim por diante.

Blocos de imagem com as somas das linhas e das colunas fixadas

Um bloco de imagem é uma matriz X, de p linhas e q colunas, cujas entradas são intensidades de pixels, todas maiores ou iguais a 0. Suponha que só se conheçam as p somas das linhas e as q somas das colunas de X. Cada soma conhecida é uma equação linear nas entradas de X, e as somas formam um sistema linear de p + q equações com pq incógnitas. O espaço nulo desse sistema é o conjunto das matrizes p × q em que todas as somas das linhas e das colunas são nulas, e se escreve N.

Um elemento de N é o padrão +1 −1 / −1 +1. Para montá-lo, escolha duas células em linhas diferentes e em colunas diferentes, que são cantos opostos de um retângulo. Ponha +1 nelas, −1 nos outros dois cantos do retângulo e 0 nas demais células. Cada linha e cada coluna do padrão contém um +1 e um −1, ou nenhum dos dois, e por isso todas as somas do padrão são nulas. Somar o padrão a X muda o bloco sem mudar nenhuma soma. Clique em dois cantos opostos do bloco e some o padrão.

O bloco X e as suas somas

À direita de cada linha aparece a soma das entradas dela. Embaixo de cada coluna aparece a soma das entradas dela. Clique em duas células que estejam em linhas diferentes e em colunas diferentes: elas são cantos opostos de um retângulo.

Uma base do espaço nulo

Bloco

Pelo teclado: clique no bloco, mova a seleção com as setas e marque a célula com Enter.

Padrão +1 −1 / −1 +1

Conceitos da aula

Resolução de Ax = 0 e Ax = b

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.2).

A eliminação de Gauss, estudada na Aula 3, leva uma matriz A a uma forma escalonada, que se escreve U. Continuando com operações elementares sobre linhas até que cada pivô seja igual a 1 e seja a única entrada não nula da sua coluna, chegamos à forma escalonada reduzida, que se escreve R. Com R, as soluções de Ax = 0 se escrevem sem substituição regressiva.

Forma escalonada reduzida

Definição

Uma matriz está na forma escalonada reduzida se:

  1. as linhas nulas, se houver, ficam abaixo de todas as linhas não nulas;
  2. a primeira entrada não nula de cada linha não nula, chamada de pivô, é igual a 1 e fica numa coluna à direita da coluna do pivô da linha de cima;
  3. em cada coluna que contém um pivô, todas as outras entradas são nulas.

Teorema

Toda matriz A pode ser levada, por operações elementares sobre linhas, a uma matriz na forma escalonada reduzida, e essa matriz é única. Ela é a forma escalonada reduzida de A, indicada por R.

Sem a exigência de que os pivôs sejam iguais a 1 e sem a condição 3, a definição é a da forma escalonada U, da Aula 3. As operações elementares sobre linhas não mudam as soluções de um sistema. Por isso, Ax = 0 e Rx = 0 têm as mesmas soluções, isto é, N(A) = N(R).

O exemplo do livro-texto

Exemplo

Na seção 2.2 do livro-texto,

A = 13322697−1−334.

Indicando por Li a linha i, a eliminação da Aula 3 chega a uma forma escalonada em três passos:

  1. L2 ← L2 − 2L1 e L3 ← L3 + L1 zeram as entradas da coluna 1 abaixo do pivô, que é 1.
  2. Abaixo da linha 1, a coluna 2 só tem zeros. Por isso ela não tem pivô, e o pivô seguinte é o 3 da linha 2, na coluna 3.
  3. L3 ← L3 − 2L2 zera a entrada abaixo desse pivô.

U = 133200330000.

Mais dois passos levam U à forma escalonada reduzida:

  1. L2 ← L2 ÷ 3 torna igual a 1 o pivô da linha 2.
  2. L1 ← L1 − 3L2 zera a entrada acima desse pivô.

R = 130−100110000.

Os pivôs de R estão nas posições (1, 1) e (2, 3), e a terceira linha é nula.

Na bancada: escolha Exemplo do livro-texto no painel Exemplos e use os botões do quadro Eliminação até R para percorrer os passos. Cada passo diz qual operação elementar foi feita. A bancada aplica as operações à matriz aumentada [A | b]: a parte de A chega a R, e a última coluna, que era b, chega a um vetor que se escreve d. A bancada segue outra ordem: em cada coluna, escolhe o pivô, trocando linhas se preciso, divide a linha do pivô por ele e zera as outras entradas da coluna. O resultado R é o mesmo, porque a forma escalonada reduzida é única.

As incógnitas se dividem em dois grupos, conforme a coluna delas em R tenha pivô ou não: as que ficam determinadas pelas outras e as que podem receber valores quaisquer.

Variáveis pivô, variáveis livres e posto

Definição

Seja A uma matriz de m linhas e n colunas, e seja R a sua forma escalonada reduzida. As colunas de R que contêm pivô são as colunas pivô. As incógnitas correspondentes a essas colunas são as variáveis pivô, e as demais incógnitas são as variáveis livres. O posto de A é o número de pivôs de R e se escreve r.

Cada linha e cada coluna de R têm no máximo um pivô. Por isso, r ≤ m e r ≤ n, e há r variáveis pivô e n − r variáveis livres. Cada linha não nula de Rx = 0 contém uma única variável pivô, com coeficiente 1, porque nas colunas dos outros pivôs essa linha tem 0. As demais incógnitas que aparecem nessa linha são livres. Assim, as variáveis livres podem receber quaisquer valores reais, e cada variável pivô fica determinada por eles.

Teorema

Se n > m, isto é, se o sistema Ax = 0 tem mais incógnitas do que equações, então ele tem uma solução diferente do vetor nulo.

De fato, r ≤ m < n, e há pelo menos uma variável livre. Dê a ela o valor 1 e dê o valor 0 às outras variáveis livres, se houver. As linhas de Rx = 0 dão as variáveis pivô, e a solução obtida tem coordenada 1 nessa variável livre. Logo ela não é o vetor nulo.

O exemplo do livro-texto

Exemplo

Na forma escalonada reduzida do exemplo da guia anterior, R = 130−100110000, os pivôs estão nas colunas 1 e 3. O posto é r = 2, as variáveis pivô são x1 e x3, e as variáveis livres são x2 e x4. As duas primeiras linhas de Rx = 0 são

x1 + 3x2 − x4 = 0,

x3 + x4 = 0,

e a terceira diz 0 = 0. Logo x1 = −3x2 + x4 e x3 = −x4, quaisquer que sejam x2 e x4.

Na bancada: no quadro Eliminação até R, abaixo da matriz, cada incógnita aparece marcada como pivô ou livre. O texto do último passo informa as colunas pivô e o posto. Na missão 1 do roteiro, você mesmo marca as variáveis livres do exemplo do livro-texto.

A cada variável livre corresponde uma solução de Ax = 0, chamada de solução especial. As soluções especiais formam uma base do espaço nulo.

Soluções especiais e o espaço nulo

Definição

Seja xj uma variável livre do sistema Ax = 0. A solução especial associada a xj é a solução de Ax = 0 em que xj = 1 e as outras variáveis livres são iguais a 0. Como na guia anterior, as variáveis pivô dela são dadas pelas linhas de Rx = 0.

Teorema

Seja A uma matriz de n colunas e posto r. O número de variáveis livres é k = n − r. Escreva as variáveis livres como xj1, …, xjk, com j1 < ⋯ < jk, e seja si a solução especial associada a xji, para i = 1, …, k. Então todo x ∈ N(A) se escreve como

x = xj1s1 + ⋯ + xjksk,

com os valores das variáveis livres de x como coeficientes. As soluções especiais s1, …, sk formam uma base de N(A), e dim N(A) = n − r.

Por quê. A prova tem três passos.

  1. Pela definição, si tem 1 na posição ji e 0 nas posições das outras variáveis livres.
  2. As soluções especiais geram N(A). Dado x ∈ N(A), seja z = x − (xj1s1 + ⋯ + xjksk). Como N(A) é um subespaço, z ∈ N(A). Pelo passo 1, a combinação linear entre parênteses tem, na posição ji, a mesma entrada que x, e por isso todas as variáveis livres de z são nulas. Com as variáveis livres nulas, as linhas de Rz = 0 dão variáveis pivô nulas. Logo z = 0.
  3. As soluções especiais são linearmente independentes. Sejam λ1, …, λk ∈ ℝ escalares com λ1s1 + ⋯ + λksk = 0. Pelo passo 1, a entrada dessa combinação linear na posição ji é λi. Logo λi = 0 para todo i.

Pelos passos 2 e 3, as k = n − r soluções especiais formam uma base de N(A). Se não há variável livre, isto é, se r = n, então N(A) = {0}.

O exemplo do livro-texto

Exemplo

Pela guia anterior, x1 = −3x2 + x4 e x3 = −x4. Com x2 = 1 e x4 = 0, obtemos a solução especial de x2, que se escreve s1. Com x2 = 0 e x4 = 1, obtemos a de x4, que se escreve s2:

s1 = (−3, 1, 0, 0)T,

s2 = (1, 0, −1, 1)T.

Assim, N(A) = {x2s1 + x4s2 : x2, x4 ∈ ℝ}, um subespaço de ℝ4 de dimensão 4 − 2 = 2. Para conferir uma das contas, o produto da primeira linha de A por s1 é 1·(−3) + 3·1 + 3·0 + 2·0 = 0.

As variáveis pivô de cada solução especial também se leem em R: são as entradas da coluna da variável livre, nas linhas dos pivôs, com o sinal trocado. A coluna 2 de R tem 3 e 0 nessas linhas, e s1 tem x1 = −3 e x3 = 0. A coluna 4 tem −1 e 1, e s2 tem x1 = 1 e x3 = −1.

Na bancada: na missão 2 do roteiro, você calcula s1 e confere As1 = 0 no painel Teste um vetor v, que mostra a conta linha por linha. Na parte Em dimensão n, o quadro As soluções especiais mostra as soluções especiais de matrizes maiores, em barras e num mapa de cores.

Quando Ax = b tem solução, todas as soluções se obtêm de uma delas, somando a ela os vetores do espaço nulo.

Solução particular e solução completa

Definição

Aplique a [A | b] as operações elementares que levam A à sua forma escalonada reduzida R. A última coluna, que era b, passa a ser um vetor que se escreve d, e a matriz obtida é [R | d]. Se o sistema tem solução, a solução particular é a solução em que todas as variáveis livres são iguais a 0. Ela se escreve xp, e nela a variável pivô da linha i de R é igual a di, a entrada i de d.

Teorema

Suponha que Ax = b tenha solução, e seja xp a solução particular. Um vetor x ∈ ℝn é solução de Ax = b se, e somente se, existe xn ∈ N(A) tal que x = xp + xn.

Por quê. Se xn ∈ N(A), então A(xp + xn) = Axp + Axn = b + 0 = b. Reciprocamente, se Ax = b, então A(x − xp) = b − b = 0, e o vetor xn = x − xp pertence a N(A). A prova só usa que Axp = b. Por isso, o teorema vale com qualquer solução de Ax = b no lugar de xp.

Definição

Sejam xj1, …, xjk as variáveis livres e s1, …, sk as soluções especiais, como na guia anterior. A solução completa de Ax = b é

x = xp + xj1s1 + ⋯ + xjksk,

para quaisquer valores reais das variáveis livres xj1, …, xjk.

Pelo teorema e pela guia anterior, essa expressão dá todas as soluções. Cada solução aparece uma única vez, pois os coeficientes são as variáveis livres dela. Quando b ≠ 0, o conjunto das soluções não é um subespaço, porque não contém o vetor nulo: A0 = 0 ≠ b.

O exemplo do livro-texto

Exemplo

Com b = (1, 5, 5)T, as operações da primeira guia levam [A | b] a [R | d], com d = (−2, 1, 0)T. Com x2 = x4 = 0, as linhas de [R | d] dão x1 = −2 e x3 = 1, e a solução particular é

xp = (−2, 0, 1, 0)T.

Com as soluções especiais s1 e s2 da guia anterior, a solução completa é

x = xp + x2s1 + x4s2,  x2, x4 ∈ ℝ.

Por exemplo, x2 = x4 = 1 dá x = (−4, 1, 0, 1)T, e de fato Ax = (1, 5, 5)T.

Na bancada: o quadro Solução completa escreve x = xp + xj1s1 + ⋯ com os vetores do sistema escolhido. Mude as variáveis livres nos controles abaixo das barras, ou arraste as barras coloridas do quadro O vetor x em barras. O vetor x muda e, quando o sistema tem solução, a conferência de Ax = b, abaixo das barras, continua valendo.

Pontos de E3 e vetores de ℝ3

Com três incógnitas, o sistema também tem uma interpretação geométrica com pontos do espaço, a imagem das linhas, estudada nas Aulas 1 e 2. Os pontos do espaço formam o espaço euclidiano, que se escreve E3. Um ponto de E3 se escreve com as suas três coordenadas, sem o T, como o ponto (2, 1, 0). O vetor (2, 1, 0)T de ℝ3 é o vetor posição desse ponto, a seta que vai da origem até ele: os dois têm as mesmas coordenadas, mas são objetos diferentes. As soluções de Ax = b e os vetores do espaço nulo N(A) pertencem a ℝ3, enquanto a imagem das linhas desenha conjuntos de pontos de E3.

Definição

Considere um sistema Ax = b com três incógnitas. Se a linha i de A não é nula, o plano da equação i é o conjunto dos pontos (x1, x2, x3) de E3 que satisfazem a equação i.

A soma de um ponto de E3 com um vetor de ℝ3 é o ponto cujas coordenadas são as do ponto somadas às do vetor. Ela é o ponto em que termina a seta do vetor quando essa seta começa no ponto dado.

Um vetor x = (x1, x2, x3)T é solução do sistema se, e somente se, o ponto (x1, x2, x3) satisfaz todas as equações. Se nenhuma linha de A é nula, isso quer dizer que esse ponto pertence aos planos de todas as equações. Pelo teorema desta guia, quando o sistema tem solução, as soluções são os vetores xp + xn, com xn ∈ N(A). Como as coordenadas de xp + xn são as de xp somadas às de xn, os pontos cujos vetores posição são soluções são as somas do ponto de vetor posição xp com os vetores de N(A). Esses pontos formam:

  • um único ponto, se N(A) = {0};
  • uma reta de E3, se N(A) é uma reta de ℝ3 que passa pela origem;
  • um plano de E3, se N(A) é um plano de ℝ3 que passa pela origem;
  • todo o E3, se N(A) = ℝ3.

Como essa reta ou esse plano de E3 se obtém somando a um ponto os vetores de N(A), diz-se que ele é paralelo a N(A). Se b ≠ 0, a origem não está entre esses pontos, porque o vetor posição dela é o vetor nulo, e A0 = 0 ≠ b. Com n incógnitas, os pontos com n coordenadas formam o conjunto En, e do mesmo modo os pontos de En cujos vetores posição são soluções são as somas do ponto de vetor posição xp com os vetores de N(A).

Exemplo

No exemplo Dois planos em E3 da bancada, as equações x1 + x2 + 2x3 = 3 e x1 + 2x2 + 3x3 = 4 descrevem dois planos de E3. A eliminação dá a solução particular xp = (2, 1, 0)T e a solução especial s1 = (−1, −1, 1)T, da variável livre x3. Os pontos cujos vetores posição são soluções são os pontos (2, 1, 0) + x3s1, com x3 ∈ ℝ, e formam a reta comum aos dois planos. Com x3 = 1, obtemos o ponto

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

que pertence aos dois planos, pois

1 + 0 + 2 · 1 = 3,

1 + 2 · 0 + 3 · 1 = 4.

A solução correspondente é o vetor (1, 0, 1)T de ℝ3, o vetor posição desse ponto. O espaço nulo N(A) = {x3s1 : x3 ∈ ℝ} é uma reta de ℝ3 que passa pela origem, formada por vetores. A reta comum aos dois planos é paralela a ela e não passa pela origem, porque b ≠ 0.

Na bancada: quando o sistema tem três incógnitas e não é um dos exemplos de rede, o primeiro quadro passa a ser Os planos das equações em E3. Escolha Dois planos em E3 no painel Exemplos: os planos das duas equações se cortam na reta preta, a reta cinza tracejada que passa pela origem representa N(A), e as setas que partem da origem são os vetores xp e s1. O vetor posição do ponto preto é o vetor x do quadro O vetor x em barras. Arraste o ponto preto ao longo da reta preta: x muda, e a conferência de Ax = b, abaixo das barras, continua valendo. As missões 6 e 7 do roteiro usam esse exemplo.

Nem todo b dá um sistema com solução. As linhas nulas de R dão as condições que b precisa satisfazer para que Ax = b tenha solução.

Quando Ax = b tem solução

Teorema

Aplique a [A | b] as operações elementares que levam A à sua forma escalonada reduzida R. A última coluna, que era b, passa a ser um vetor que se escreve d. O sistema Ax = b tem solução se, e somente se, di = 0 em toda linha i em que R é nula. Em particular, se o posto r é igual ao número m de linhas de A, então R não tem linha nula, e Ax = b tem solução para todo b ∈ ℝm.

Por quê. Se a linha i de R é nula, a equação dessa linha em [R | d] é 0 = di. Se di ≠ 0, nenhum vetor satisfaz essa equação, e o sistema não tem solução. Se todas as linhas nulas têm di = 0, a solução particular satisfaz todas as equações: as variáveis livres valem 0, e a variável pivô de cada linha não nula vale a entrada de d nessa linha.

Como d é obtido de b pelas mesmas operações, cada di é uma combinação linear das entradas de b. Numa linha nula de R, a equação di = 0 é uma condição de solvabilidade: uma combinação linear das entradas de b que precisa ser nula. Como R tem m − r linhas nulas, há m − r condições. Um sistema que tem solução é chamado de compatível, e um sistema sem solução, de incompatível.

Comparando o posto r com o número m de equações e o número n de incógnitas, há quatro casos:

  • se r = m = n, há exatamente uma solução para cada b;
  • se r = m < n, há infinitas soluções para cada b;
  • se r = n < m, há uma única solução ou nenhuma, conforme b;
  • se r < m e r < n, há infinitas soluções ou nenhuma, conforme b.

O exemplo do livro-texto

Exemplo

Com um b qualquer, as operações da primeira guia levam a terceira linha de [A | b] à equação

0x1 + 0x2 + 0x3 + 0x4 = 5b1 − 2b2 + b3.

Indicando por Li a linha i de [A | b], essa linha final é a combinação linear 5L1 − 2L2 + L3, que anula a parte de A. Logo Ax = b tem solução se, e somente se, 5b1 − 2b2 + b3 = 0. Para b = (1, 5, 5)T,

5 · 1 − 2 · 5 + 5 = 0,

e há solução. Para b = (1, 5, 4)T, a mesma conta dá −1, e a última linha de [R | d] diz 0 = −1.

Na bancada: a última leitura do quadro Solução completa mostra as condições de solvabilidade do sistema escolhido, se houver, e confere se o b atual as satisfaz. Na missão 5 do roteiro, você muda b3 no painel Sistema [A | b] até o sistema ter solução. A missão 7 pergunta o que acontece quando o posto é igual ao número de equações.

O primeiro exemplo da bancada é uma rede de computadores. Nela, cada solução especial é um fluxo que percorre um caminho fechado da rede, e a condição de solvabilidade diz que a quantidade que entra na rede é igual à que sai dela.

A matriz de incidência

Definição

Considere uma rede de m nós e n ligações, em que cada ligação tem um sentido de referência, de um nó de saída para um nó de chegada. A matriz de incidência da rede é a matriz G, de tamanho n × m, com uma linha por ligação e uma coluna por nó: na linha da ligação j, a entrada é −1 na coluna do nó de saída, 1 na coluna do nó de chegada e 0 nas outras. É a convenção do livro-texto, usada também na Aula 9.

O fluxo na ligação j se escreve xj. Ele é positivo quando vai no sentido de referência e negativo quando vai no sentido oposto. A quantidade que sai da rede pelo nó i se escreve bi, e é negativa quando a quantidade entra na rede por esse nó. Em cada nó, o fluxo que chega pelas ligações menos o fluxo que sai por elas é igual ao que sai da rede por esse nó.

A linha i de GT tem 1 nas ligações que chegam ao nó i e −1 nas que saem dele. Por isso, (GTx)i é o fluxo que chega ao nó i menos o fluxo que sai dele, e o sistema dos fluxos é GTx = b. Na bancada, a matriz do sistema é A = GT, de tamanho m × n: uma equação por nó e uma incógnita por ligação.

Cada linha de G tem um −1 e um 1. Logo cada coluna de A tem soma 0, e a soma das linhas de A é a linha nula. Somando as m equações, obtemos 0 = b1 + ⋯ + bm. Essa é uma condição de solvabilidade: a quantidade que entra na rede precisa ser igual à que sai dela.

Um fluxo em que, em cada nó, chega o mesmo que sai se chama circulação. As circulações são exatamente as soluções de Ax = 0. Um ciclo é um caminho que sai de um nó, passa por ligações distintas sem repetir nó e volta ao nó de partida. Ao longo do caminho, cada ligação pode ser percorrida no seu sentido de referência ou no sentido oposto. A circulação de uma unidade ao longo de um ciclo vale 1 nas ligações percorridas no sentido de referência, −1 nas percorridas no sentido oposto e 0 nas outras.

A outra convenção. Alguns textos chamam de matriz de incidência a matriz com uma linha por nó e uma coluna por ligação, isto é, a transposta GT, às vezes com os sinais trocados. As duas descrevem a mesma rede. Na Aula 9, a matriz estudada é a própria matriz de incidência, e as circulações formam o espaço nulo à esquerda dela. Aqui, como a matriz do sistema é A = GT, elas formam o espaço nulo N(A).

A rede da bancada

Exemplo

A rede tem quatro servidores, S1 a S4, e seis ligações. A ligação 1 vai de S1 a S2, a 2 vai de S1 a S3 e a 3 vai de S2 a S3. A ligação 4 vai de S2 a S4, a 5 vai de S3 a S4 e a 6 vai de S4 a S1. A matriz de incidência G, com uma linha por ligação, e a matriz do sistema A = GT, com uma linha por servidor, são

G = −1100−10100−1100−10100−11100−1,

A = GT = −1−1000110−1−1000110−1000011−1.

A eliminação dá pivôs nas colunas 1, 2 e 4. O posto é 3, e as variáveis livres são x3, x5 e x6. A solução especial de x6, a terceira variável livre, se escreve s3:

s3 = (1, 0, 0, 1, 0, 1)T.

Ela é a circulação de uma unidade ao longo do ciclo S1 → S2 → S4 → S1, que usa as ligações 1, 4 e 6, todas no sentido de referência. As outras duas soluções especiais também são circulações de uma unidade ao longo de ciclos, como mostra a primeira pergunta de Para pensar. Como há 4 equações e o posto é 3, R tem 4 − 3 = 1 linha nula, e a única condição de solvabilidade é b1 + b2 + b3 + b4 = 0.

Na bancada: escolha Rede de pacotes no painel Exemplos. No quadro A rede de pacotes, cada seta mostra o sentido do fluxo e fica mais larga quando o valor absoluto do fluxo cresce, até um limite. Cada servidor fica verde quando a sua equação é satisfeita e vermelho quando não é. Com a opção Destacar o ciclo de cada solução especial marcada no painel O que mostrar, passe o mouse sobre o controle de uma variável livre, abaixo das barras: as ligações do ciclo da solução especial dela ficam destacadas. Nas missões 3 e 4 do roteiro, você percorre um ciclo e divide o fluxo de um pacote entre dois caminhos.

Para pensar

Na rede de pacotes, por que as soluções especiais são circulações ao longo de ciclos?

Chame de ligações pivô as ligações cujos fluxos são variáveis pivô, aqui as ligações 1, 2 e 4, e de ligações livres as outras, 3, 5 e 6. O argumento tem três passos.

  1. As ligações pivô ligam os quatro servidores sem formar ciclo: a 1 liga S1 a S2, a 2 liga S1 a S3 e a 4 liga S2 a S4. Cada ligação livre, junto com ligações pivô, forma um ciclo. A ligação 3 forma S1 → S2 → S3 → S1, a 5 forma S1 → S3 → S4 → S2 → S1, e a 6 forma S1 → S2 → S4 → S1.
  2. Percorra o ciclo de uma ligação livre no sentido de referência dela. A circulação de uma unidade ao longo desse ciclo é uma solução de Ax = 0. Nela, essa variável livre vale 1, e as outras variáveis livres valem 0, porque o ciclo não usa as outras ligações livres.
  3. Fixados os valores das variáveis livres, as linhas de Rx = 0 determinam as variáveis pivô de um único modo. Logo essa circulação é a solução especial da variável livre.

Assim, a solução especial de x3 é s1 = (1, −1, 1, 0, 0, 0)T, com −1 na ligação 2, que o ciclo percorre de S3 a S1, no sentido oposto ao de referência. A de x5 é s2 = (−1, 1, 0, −1, 1, 0)T, e a de x6 é s3 = (1, 0, 0, 1, 0, 1)T.

Um sistema de 3 equações e 5 incógnitas pode ter solução única?

Não. O posto r é o número de pivôs, e cada uma das 3 linhas de R tem no máximo um pivô. Logo r ≤ 3, há pelo menos 5 − 3 = 2 variáveis livres, e dim N(A) ≥ 2. Se o sistema tiver uma solução, somar a ela qualquer vetor do espaço nulo dá outra solução. Como N(A) tem infinitos vetores, as soluções são infinitas. O sistema também pode não ter solução, quando r < 3 e b não satisfaz as condições de solvabilidade.

Com b ≠ 0, o conjunto das soluções de Ax = b é um subespaço de ℝn?

Não, porque não contém o vetor nulo: A0 = 0 ≠ b. A soma de duas soluções também não é solução: se Ax = b e Ax′ = b, então A(x + x′) = 2b, que é diferente de b porque b ≠ 0. Quando há solução, seja xp a solução particular, a que tem as variáveis livres iguais a 0. O conjunto das soluções é {xp + xn : xn ∈ N(A)}, formado pelos vetores que se obtêm somando xp a cada vetor do espaço nulo. Com três incógnitas, os pontos do espaço euclidiano E3 cujos vetores posição são as soluções formam um único ponto, uma reta ou um plano de E3, e a origem não está entre eles, como mostra a guia Solução completa.