TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1

Statement

Let $p \in Q$ with $p \geq 1$ and let $m, n, q \in N$ , with the induced $p$ -norms of The matrix norm induced by a published vector p-norm.

Compatibility. For every $A \in M_{m \times n} (R)$ and every $x \in R^{n}$ , $∥ A x ∥_{p} \leq ∥ A ∥_{p} ∥ x ∥_{p} .$
Submultiplicativity. For every $A \in M_{m \times n} (R)$ and $B \in M_{n \times q} (R)$ , $∥ A B ∥_{p} \leq ∥ A ∥_{p} ∥ B ∥_{p} .$
Normalisation. For every $n \geq 1$ , $∥ I_{n} ∥_{p} = 1,$ where $I_{n}$ is the identity matrix of Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes; at $n = 0$ the unique empty matrix $I_{0} \in M_{0} (R)$ has $∥ I_{0} ∥_{p} = 0$ , the convention of The matrix norm induced by a published vector p-norm.

Facts & Assumptions

Given: A rational $p \geq 1$ , natural numbers $m, n, q$ , matrices $A \in M_{m \times n} (R)$ , $B \in M_{n \times q} (R)$ , and vectors $x \in R^{n}$ .

[L1]

$∥ \cdot ∥_{p}$ is a norm on $R^{n}$ and on $R^{m}$ : in particular $∥ 0 ∥_{p} = 0$ and $∥ λ y ∥_{p} = ∣ λ ∣ ∥ y ∥_{p}$ (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 $∥ A ∥_{p} = \sup {∥ A y ∥_{p} : ∥ y ∥_{p} \leq 1}$ (The matrix norm induced by a published vector p-norm).

[L3]

Matrix multiplication is associative, so $(A B) x = A (B x)$ ; it is also unital, so $I_{n} x = x$ for $n \geq 1$ (Matrix multiplication is associative, unital, distributive, and compatible with scalar multiplication, Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes).

Proof

technique · direct

1.1L1L2algebra

For $x = 0$ the compatibility claim reads $0 \leq ∥ A ∥_{p} \cdot 0$ , which is true by [L1] and [L2].

1.2L1algebra

For $x \neq 0$ the vector $∥ x ∥_{p} > 0$ by [L1], so $∥ A x ∥_{p} / ∥ x ∥_{p} = ∥ A (x / ∥ x ∥_{p}) ∥_{p}$ by homogeneity of [L1].

1.3L1L2L3algebra

For claim 2, if $q = 0$ , then $B \in M_{n \times 0} (R)$ and $A B \in M_{m \times 0} (R)$ are empty matrices. Their domains contain only the zero vector, so the unit-ball definition [L2] gives $∥ B ∥_{p} = ∥ A B ∥_{p} = 0$ . Thus $∥ A B ∥_{p} = 0 = ∥ A ∥_{p} ∥ B ∥_{p}$ , proving claim 2 in this case without a ratio supremum.

1.4L2L3algebra

For $n \geq 1$ every $x \neq 0$ attains ratio one: by [L3], $∥ I_{n} x ∥_{p} = ∥ x ∥_{p}$ , so $∥ I_{n} x ∥_{p} / ∥ x ∥_{p} = 1$ , and the supremum in [L2] is therefore $1$ , which is claim 3 for $n \geq 1$ .

1.5L2algebra

At $n = 0$ the space $R^{0}$ has only the zero vector, so the definition of The matrix norm induced by a published vector p-norm assigns $∥ I_{0} ∥_{p} = 0$ , which is the stated exceptional value.

2.1step 1.2L2algebra

The scaled vector $x / ∥ x ∥_{p}$ has $p$ -norm $1$ , so $∥ A (x / ∥ x ∥_{p}) ∥_{p} \leq ∥ A ∥_{p}$ by [L2]; combining step 1.2 with this bound gives $∥ A x ∥_{p} \leq ∥ A ∥_{p} ∥ x ∥_{p}$ , which with step 1.1 proves claim 1.

3.1step 2.1L3algebra

For the remaining case $q \geq 1$ , let $x \in R^{q}$ with $x \neq 0$ . Associativity of [L3] gives $∥ (A B) x ∥_{p} = ∥ A (B x) ∥_{p}$ , and applying claim 1 first to $A$ at the vector $B x$ and then to $B$ at the vector $x$ gives $∥ A (B x) ∥_{p} \leq ∥ A ∥_{p} ∥ B x ∥_{p} \leq ∥ A ∥_{p} ∥ B ∥_{p} ∥ x ∥_{p}$ .

4.1step 3.1L1L2algebra

Still assuming $q \geq 1$ , dividing step 3.1 by the positive number $∥ x ∥_{p}$ and taking the supremum over all nonzero $x$ in the definition of [L2] gives $∥ A B ∥_{p} \leq ∥ A ∥_{p} ∥ B ∥_{p}$ ; with step 1.3 this is claim 2.

5.1step 2.1step 1.3step 4.1step 1.4step 1.5∎

Claim 1 is step 2.1. Claim 2 follows from step 1.3 when $q = 0$ and step 4.1 when $q \geq 1$ . Claim 3 is steps 1.4 and 1.5.

Depends on

Dependency tree · 2 levels

Sources

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