TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-08-29

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The induced 1-norm is the maximum column sum and the induced infinity-norm is the maximum row sum

Statement

Let $m, n \in N$ with $m \geq 1$ and $n \geq 1$ , and let $A = (a_{i j}) \in M_{m \times n} (R)$ , with the induced $1$ -norm and the separately defined induced $\infty$ -norm of The matrix norm induced by a published vector p-norm.

Maximum column sum. $∥ A ∥_{1} = \max_{j < n} \sum_{i < m} ∣ a_{i j} ∣$ .
Maximum row sum. $∥ A ∥_{\infty} = \max_{i < m} \sum_{j < n} ∣ a_{i j} ∣$ .

Facts & Assumptions

Given: Natural numbers $m, n \geq 1$ , a matrix $A = (a_{i j}) \in M_{m \times n} (R)$ , and vectors $x = (x_{j}) \in R^{n}$ .

[L1]

The $1$ -norm and the $\infty$ -norm are $∥ x ∥_{1} = \sum_{j < n} ∣ x_{j} ∣$ and $∥ x ∥_{\infty} = \max {∣ x_{j} ∣ : j < n}$ (The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$ ); each is a norm, in particular the triangle inequality and $∣ x_{j} ∣ \leq ∥ x ∥_{\infty}$ hold (Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page).

[L2]

The induced norm is the supremum of the ratio over nonzero vectors, and compatibility gives $∥ A x ∥_{p} \leq ∥ A ∥_{p} ∥ x ∥_{p}$ (The matrix norm induced by a published vector p-norm, Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1).

[L3]

The standard basis vector $e_{j} \in R^{n}$ satisfies $e_{j} (j) = 1$ and $e_{j} (k) = 0$ for $k \neq j$ , and finite sums are evaluated pointwise; in particular $(A e_{j})_{i} = a_{i j}$ (The standard list $e : n \to F^{n}$ with $e_{i} (i) = 1_{F}$ and $e_{i} (j) = 0_{F}$ for $j \neq i$ is an ordered basis of $F^{n}$ ; hence $\dim_{F} F^{n} = n$ , and $F^{0}$ is the zero space with basis $\emptyset$ and dimension $0$ ).

Proof

technique · direct

1.1givenL1

Write $C : = \max_{j < n} \sum_{i < m} ∣ a_{i j} ∣$ ; the maximum exists because it is a maximum of the nonempty finite set of column sums of [L1].

1.2L1algebra

Expanding the matrix-vector product entrywise and using the triangle inequality and absolute multiplicativity of [L1] gives $∥ A x ∥_{1} = \sum_{i < m} ∣ \sum_{j < n} a_{i j} x_{j} ∣ \leq \sum_{i < m} \sum_{j < n} ∣ a_{i j} ∣ ∣ x_{j} ∣$ .

1.3L1

Write $R : = \max_{i < m} \sum_{j < n} ∣ a_{i j} ∣$ , a maximum of a nonempty finite set of row sums by [L1].

2.1step 1.2step 1.1L1algebra

Exchanging the finite double sum in step 1.2 and bounding every column sum by $C$ from step 1.1 gives $∥ A x ∥_{1} \leq \sum_{j < n} (\sum_{i < m} ∣ a_{i j} ∣) ∣ x_{j} ∣ \leq C \sum_{j < n} ∣ x_{j} ∣ = C ∥ x ∥_{1}$ .

2.2step 1.1choose

Choose $j^{*} < n$ attaining the maximum column sum, so $\sum_{i < m} ∣ a_{i j^{*}} ∣ = C$ , which exists by step 1.1.

2.3L1step 1.3algebra

For every $i < m$ , $∣ (A x)_{i} ∣ = ∣ \sum_{j < n} a_{i j} x_{j} ∣ \leq \sum_{j < n} ∣ a_{i j} ∣ ∣ x_{j} ∣ \leq (\sum_{j < n} ∣ a_{i j} ∣) ∥ x ∥_{\infty} \leq R ∥ x ∥_{\infty}$ , using the triangle inequality, $∣ x_{j} ∣ \leq ∥ x ∥_{\infty}$ and the definition of $R$ .

2.4step 1.3choose

Choose $i^{*} < m$ attaining the maximum row sum: $\sum_{j < n} ∣ a_{i^{*} j} ∣ = R$ , which exists by step 1.3.

3.1step 2.1L2

By [L2] the induced norm is the supremum of the ratio over nonzero $x$ , so step 2.1 gives $∥ A ∥_{1} \leq C$ .

3.2L1L3step 2.2

For the standard basis vector $e_{j^{*}}$ of [L3], $∥ e_{j^{*}} ∥_{1} = 1$ and $∥ A e_{j^{*}} ∥_{1} = \sum_{i < m} ∣ a_{i j^{*}} ∣ = C$ , so the ratio $∥ A e_{j^{*}} ∥_{1} / ∥ e_{j^{*}} ∥_{1} = C$ is attained and $∥ A ∥_{1} \geq C$ .

3.3step 2.3L1L2

Taking the maximum over $i < m$ in step 2.3 gives $∥ A x ∥_{\infty} \leq R ∥ x ∥_{\infty}$ , and by [L2] the induced $\infty$ -norm is at most $R$ .

3.4L1L3step 2.4algebra

Define $x \in R^{n}$ by $x_{j} : = 1$ when $a_{i^{*} j} \geq 0$ and $x_{j} : = - 1$ when $a_{i^{*} j} < 0$ ; then $∥ x ∥_{\infty} = 1$ and $(A x)_{i^{*}} = \sum_{j < n} a_{i^{*} j} x_{j} = \sum_{j < n} ∣ a_{i^{*} j} ∣ = R$ , by [L1] and [L3].

4.1step 3.1step 3.2

Steps 3.1 and 3.2 give $∥ A ∥_{1} = C$ , which is claim 1.

4.2step 3.4step 3.3L2

The vector $x$ of step 3.4 attains the ratio $R$ , so $∥ A ∥_{\infty} \geq R$ ; with step 3.3 this gives $∥ A ∥_{\infty} = R$ , which is claim 2.

5.1step 4.1step 4.2∎

Claims 1 and 2 are steps 4.1 and 4.2.

Depends on

Dependency tree · 2 levels

Sources

James Demmel, Math 221 Lecture 3: Vector Norms, Matrix Norms, and Condition Numbers