This section develops linear algebra from the axioms, assuming only the
notion of a field (4): vector spaces, whose
elements can be added and scaled by elements of a field; bases and
dimension (Theorem 8.17); linear maps and
rank–nullity (Theorem 8.19); bilinear forms and
the standard inner product on the coordinate space , in practice
over a finite field ; and the mixed inner product of a vector of
scalars with a vector of group elements. For fixed public elements
The section also discharges two deferrals. Remark 5.5 left to it the linear structure of , with the monomials as an infinite coordinate system. The proof of Theorem 6.10 used two facts without proof: a space with a finite spanning set has a basis, proved in Theorem 8.17, and coordinates in a basis are unique, which follows from linear independence (Definition 8.14). Neither argument uses finite fields, so no circularity arises. Throughout, denotes an arbitrary field with identities and ; the field axioms of Definition 4.24 are used without citation.
Let be a field. A vector space over (an
-vector space) is a set equipped with two operations,
vector addition
scalar multiplication is compatible with the multiplication of
:
the identity of acts as the identity:
scalar multiplication distributes over vector addition:
scalar multiplication distributes over scalar addition:
The elements of are called vectors, the elements of
scalars. We write for
The following consequences of the axioms are used hereafter without citation.
Let be an -vector space,
if
(1) By distributivity over scalar addition,
(2) Likewise
(3) Using the identity axiom, distributivity, and (1),
so
(4) Suppose
the last step by (2). □
The principal example is the coordinate space
the set of -tuples of scalars, under componentwise operations:
The zero vector is , and every axiom of
8.1 follows from the corresponding field axiom applied
in each coordinate. The degenerate case
Polynomials. The polynomials form an -vector space under addition and the scalar multiplication of Remark 5.5. So does the subset
of polynomials of degree less than : sums and scalar multiples of such polynomials again have degree less than (or are zero), by Proposition 5.7, so the operations restrict and the axioms are inherited. Polynomial commitment schemes operate on this space.
Functions. For any set , the set of all
functions
Matrices. The set of
Field extensions. If is a subfield of a larger field
(§4), then is an -vector space:
vector addition is the addition of , and scalar multiplication is
the multiplication of restricted to pairs in
A subset
A subset
is closed under addition:
is closed under scalar multiplication:
Equivalently, is a subspace if and only if
If is a subspace, then (1)–(3) hold: closure (2) and (3) is what
it means for the inherited operations to be operations on ,
and the zero vector of is the zero vector of , since a zero
vector of satisfies
Conversely, suppose (1)–(3) hold. Closure makes the two operations well
defined on . The additive inverse of any
For the two-scalar form: if is a subspace, then
In the set
Let be an -vector space.
The intersection of an arbitrary family of subspaces of is a subspace.
The sum
The union of two subspaces is in general not a subspace.
(1) Each contains , so the intersection does. If
(2) The sum contains
and
For the union, take
Besides being cut out by equations, a subspace can be generated by a set of vectors, as the set of all vectors obtained from them by addition and scaling.
Let
The span of , written or
, is the set of all linear combinations of finitely
many vectors of ; by convention
For any
The zero vector is the empty linear combination (or, for nonempty ,
the combination ), and a sum of two linear combinations of
vectors in , or a scalar multiple of one, is again such a linear
combination—concatenate the lists and rescale the coefficients. By
Proposition 8.6, is a
subspace, and it contains each
A finite list of vectors
Otherwise the list is linearly dependent, and a relation
Linear independence expresses non-redundancy: a list is dependent
exactly when some vector in it lies in the span of the others, which is
the content of the next lemma. A single vector is independent if
and only if
A list
Suppose first that
is a dependence relation, its coefficient on being
nonzero (as
For the second statement, take a dependence relation
A basis of is a linearly independent set that spans
. Every
and call the scalars the coordinates of in .
The standard basis of is
That all bases of a space have the same length rests on the following lemma, whose proof replaces the vectors of a spanning list, one at a time, by the vectors of an independent list.
If
We prove by induction on
spans . The case
For the induction step, suppose the hybrid list at stage
Some coefficient with
Every vector of the stage- list therefore lies in the span of the
stage-
Each step replaces one by one , so the induction reaches
Let be a finitely generated -vector space. Then has a
basis, and any two bases of have the same number of elements. This
common number is the dimension (written
when the field is clear). In particular
Existence. Let
Invariance. Every basis is finite: if a basis contained more than
the elements of a finite spanning list, any
The two named spaces have the explicit bases of Example 8.15, each of length . □
Linear maps are the functions between vector spaces that preserve the linear structure; the Pedersen-style commitments of the series are such maps.
A function
Its kernel and image are
A bijective linear map is an isomorphism.
Three basic facts follow from the subspace criterion and linearity.
First, taking
Let
The kernel is a subspace of the finite-dimensional , and is itself
finite-dimensional: an independent list in has length at most
by Lemma 8.16 (tested against a basis of
, which spans), so a longest independent
list
Extend it to a basis of : while the current independent list fails
to span , adjoin any vector outside its span—independence is
preserved by Lemma 8.13—and the process
terminates, again because independent lists cannot exceed
in length (Lemma 8.16 against any basis
of ). Write the resulting basis as
We claim
Spanning. Any element of is for some
Independence. Suppose
Rank–nullity implies that a linear map from a higher-dimensional space into a lower-dimensional one has a nontrivial kernel—the image has dimension at most that of the target, so the kernel has dimension at least the difference—and therefore that distinct inputs collide. This collision is what makes vector commitments compressing and only computationally binding (Remark 8.29).
Commitment and proof systems use expressions linear in each of two arguments, chiefly the inner product of two vectors. Over a finite field such a product has no length, angle or positivity, and the applications use only its algebraic properties, which the bilinear form captures.
A bilinear form on an -vector space is a function
for all
Relative to a fixed basis
The standard inner product (or dot product) on is
Bilinearity holds because each term is linear in each
factor, and symmetry because multiplication in commutes; the
representing array in the standard basis is the identity
( is if
Over the standard inner product is positive definite:
in . The arguments of proof systems use only the algebraic properties that remain—bilinearity, symmetry, and nondegeneracy—so the absence of positivity does not affect them.
Nondegeneracy identifies vectors with the scalar-valued linear maps on them.
For each
is an isomorphism of -vector spaces onto the dual space of all linear functionals on . In particular both spaces have dimension .
Each
so
By Proposition 8.23, the notions “a linear
functional on ” and “a vector in ” are interchangeable.
For a fixed point
Evaluating a committed polynomial at a challenge point is therefore an inner-product claim about the committed coefficient vector, which is the form of statement an inner-product argument proves (8.32).
The commitments of Halo 2 and Orchard pair a vector of scalars with a vector of group elements. This subsection develops their algebra over an abstract abelian group; the group used in practice, the points of an elliptic curve, is constructed in the elliptic-curve section later in the volume, and the results apply to it unchanged.
Let
Let be an abelian group of prime order , with the scalar
multiplication of 8.25. Then is an
-vector space of dimension ; any element
The vector-space axioms are the standard laws of multiples. For
integers
Now let
Let
The angle-bracket notation of 8.21 is reused; the type of the second argument—scalar vector or vector of group elements—determines which product is meant.
Fix
Symmetrically, for fixed
Both statements are the vector-space laws of (Proposition 8.26) applied componentwise. For the first,
using
The element is a commitment to the
scalar vector under the public “basis”
, as at the opening of the section.
Proposition 8.28 is its homomorphic
property: the commitment
to
which is moreover perfectly hiding: for fixed , as ranges uniformly over the term ranges uniformly over (it is a bijection of , by unique representation in the basis ), so the commitment’s distribution is uniform and carries no information about .
The following remarks locate the preceding results in commitment and proof systems. They are descriptive; later volumes develop each point rigorously.
An arithmetic circuit over becomes, after
arithmetisation—the encoding of a computation as a system of
polynomial constraints on the wire values—a collection of equations
that the vector
A Pedersen vector commitment
The core statement an inner-product argument proves has the form:
“I know vectors
for public