Dual spaces lie at the core of linear algebra and allow us to reason formally about duality in mathematics. Duality appears naturally in measure theory, functional analysis, and mathematical optimization. In this post, I explore dual spaces and their interpretation in linear algebra, motivated by the so-called convex conjugate, or Fenchel conjugate, in mathematical optimization.
For the sake of abstractness and general applicability, we will consider that we are in a general field π½ which for example can be β, β etc. Our space of vectors, is the vector space V, which in general can be subspace of π½π for some π ββ for example.
Dual spaces
Dual space - The dual space Vβ of the vector space V, is the set of all linear transformations π from V to π½ denoted as Vβ =β(V,π½).
Linear functionals - An element π :V βπ½ of Vβ is called a linear functional, which takes in a vector π₯ βV, and outputs an element in π½.
Note that if π,π βVβ, then πΌπ +π½π is also in Vβ for πΌ,π½ βπ½ and would be defined as (πΌπ +π½π)(π₯) =πΌπ(π₯) +π½π(π₯) for all π₯ βV. Let us look at a few examples :
- If V =Pπ is the space of all univariate polynomial over the field β with degree π ββ, then π defined as π(π) =π(1) +2πβ²(0), is a linear functional contained in Vβ =β(Pπ,β).
- If V =βπΓπ be the space of all real matrices of size π Γπ, then π defined as π(π) =Tr[π], is a linear functional contained in Vβ =β(βπΓπ,β).
- If V =C([βπ,π]) is the space of all real valued continuous functions on [βπ,π], then π defined as π(π) =β«πβππ(π₯)cosβ‘(2π₯)ππ₯, is a linear functional contained in Vβ =β([βπ,π],β). This function essentially outputs the 2nd Fourier coefficient of its input function.
Dual basis
Let V be a finite dimensional vector space, and π½ ={π£π}ππ=1 be a basis of V. Therefore, to determine the action of any linear functional π βVβ, it is enough to know its action on the basis vectors {π£π}ππ=1, i.e., it is enough to know what {π(π£π)βπ½}ππ=1 are.
Dual basis - If V is finite dimensional and π½ ={π£π}ππ=1 is a basis of V, then π½β ={ππ}ππ=1, the set of functionals defined by ππ(π£π) =πΏππΒ βΒ π,π β[π], is the corresponding basis of Vβ also known as a dual basis of V.
To verify that π½β is indeed a basis of Vβ, we just need to check the following
- π½β is a linearly independent set of linear functionals, i.e., if πβπ=1ππππ =π0 for some set {ππβπ½}ππ=1, then ππ =0Β βΒ π β[π], where π0 is the 0 functional. To verify this, we just need to check this condition for all the basis elements of V, π£ βπ½, which gives us πβπ=1ππππ(π£π) =0Β βΒ π β[π], and implies that ππ =0Β βΒ π β[π] establishing the linear independence of the set π½β.
- π½β spans Vβ, i.e., for any π βVβ, we have some set of elements {ππβπ½}ππ=1 such that π(π£) =πβπ=1ππππ(π£)Β βΒ π£ βV. To check this, we evaluate π on basis vectors π£π βπ½ for π β[π], which gives us π(π£π) =πβπ=1ππππ(π£π) =πβπ=1πππΏππ =ππΒ βΒ π β[π], or, ππ =π(π£π)Β βΒ π β[π]. Therefore, if π is in the span of π½β, then it must be the case that the coefficients satisfy ππ =π(π£π)Β βΒ π β[π]. Now, if π =πβπ=1π(π£π)ππ, then to show that π =π, it is enough to show that they agree on the basis vectors {π£π} of V, that is π(π£π) =π(π£π). This is simply true by the construction of {ππ}ππ=1, therefore π½β spans Vβ.
This establishes that π½β ={ππ}ππ=1 is indeed a basis of Vβ, and any π βVβ can be decomposed into the basis of Vβ as
π=πβπ=1π(π£π)ππ
where π½ ={π£π} is the basis of V. The existence of dual basis π½β and the relation with π½ also shows that V and Vβ are isomorphic.
Transpose
The existence of the dual basis π½β helps us define the concept of transpose in linear algebra which is extensively used in application.
Transpose - Let π :V βW be a linear transformation from the vector space V to the vector space W, then πβ€ :Wβ βVβ is a linear transformation from Wβ to Vβ that takes in a linear functional π βWβ, and outputs another linear functional πβ€(π) βVβ defined as πβ€(π)(π₯) =π(π(π₯))Β βΒ π₯ βV.
π₯πβπ(π₯)πβWβββββββββββΒ π(π(π₯))β‘π₯πβ€(π)βVββββββββββββββββπ(π(π₯))VπβWπβWβββββββββββΒ π½Vπβ€(π)βVββββββββββββββββπ½ Theorem - Let π :V βW be a linear transformation from vector space V to vector space W. Let π½ ={π£π}ππ=1 and π½β ={ππ}ππ=1 be the basis of V and Vβ respectively, and πΎ ={π€π}ππ=1 and πΎβ ={ππ}ππ=1 be the basis of W and Wβ respectively. Let π΄ =[π]πΎπ½ be the matrix which transforms a vector in V to a vector in W. Then [πβ€]π½βπΎβ =π΄β€.
The matrix of [πβ€]π½βπΎβ takes in an element of Wβ represented in its basis πΎβ, and outputs an element in Vβ represented in its basis π½β. Therefore, it is sufficient to represent every element in {πβ€(ππ)}ππ=1 in the basis π½β of Vβ. Since any vector π in Vβ can be expressed as a linear combination of the basis vectors π½β as we proved earlier, we have
πβ€(ππ)=πβπ=1πβ€(ππ)(π£π)ππ=πβπ=1ππ(π(π£π))ππ Therefore, the (π,π)-th element of the matrix [πβ€]π½βπΎβ is ππ(π(π£π)). Now, the elements of the matrix [π]πΎπ½ are the representations of the basis vectors π½ of V, in the basis vectors πΎ of W. Therefore we have,
π(π£π)=πβπ=1π΄πππ€πβΉππ(π(π£π))=ππ(πβπ=1π΄πππ€π)=πβπ=1π΄ππππ(π€π)(β΅πΒ is a linear functional)=π΄ππ(β΅ππ(π€π)=πΏππ) Which finally gives us
πβ€(ππ)=πβπ=1π΄ππππ and shows us that the (π,π)-th element of the matrix [πβ€]π½βπΎβ is nothing but the (π,π)-th element of π΄, which implies that the matrix [πβ€]π½βπΎβ =π΄β€.
Double Dual
If V is a vector space, then its dual space Vβ is also a vector space. We can again define the set of all linear transformations from Vβ to π½ as its dual space Vββ =β(Vβ,π½), which makes it the double dual space of V. Unlike Vβ where we needed to define basis, there is an elegant way to go from V to Vββ via an injective map Ξ¨. If π₯ βV, and Λπ₯ =Ξ¨(π₯) βVββ acts on a linear functional π βVβ and evaluates π at π₯ returning an element in the field π½, i.e.,
πΛπ₯βVββββββββββββπ(π₯)VβΛπ₯βVββββββββββββπ½ Theorem - If V is a vector space of finite dimension, then Ξ¨ :V βVββ is an isomorphism. First, we show that Ξ¨ is linear. If π₯,π¦ βV, π βVβ, and π βπ½, then
Ξ¨(π₯+ππ¦)(π)=π(π₯+ππ¦)=π(π₯)+ππ(π¦)=(Ξ¨(π₯)+πΞ¨(π¦))(π) Next, we show that Ξ¨ is one to one. Suppose Λπ₯ =0, the zero functional, then π₯ =0. Let π½ ={π£π}ππ=1, then π₯ =πβπ=1πππ£π for some {ππβπ½}. Therefore, if Ξ¨(π₯) =Λπ₯ =0, then
Ξ¨(π₯)=Ξ¨(πβπ=1πππ£π)=πβπ=1ππΞ¨(π£π)βΉΞ¨(π₯)(π)=πβπ=1ππΞ¨(π£π)(π)βΒ πβVβ=πβπ=1πππ(π£π) For π β{ππ}ππ=1, we get ππ =0Β βΒ π β[π]. This implies that π₯ =πβπ=1πππ£π =0. Since dim(V) =dim(Vββ), we have that Ξ¨ is one to one and therefore an isomorphism. The isomorphism between V and Vββ, Ξ¨, allows us to map each element in V to a unique element in Vββ.
The infinite sequence of dual spaces
We can continue thinking about the dual of the parent space and there always will exist an isomorphism between alternate dual spaces. Formally, Let us denote V(π+1)β =(V(π)β)β for all π ββ where V(0)β =V is a finite dimensional vector space. Let Ξ¨π be the isomorphism between V(πβ1)β and V(π+1)β. Then, in general define Λπ₯(π+1) =Ξ¨π(Λπ₯(πβ1)) for Λπ₯(πβ1) βV(πβ1)β when π is odd, and Λπ(π+1) =Ξ¨π(Λπ(πβ1)) for Λπ(πβ1) βV(πβ1)β when π is an even natural number, with Λπ₯(0) =π₯ βV, and Λπ(1) =π βVβ. Then by the property of these isomorphisms we have
Λπ₯(π+1)(Λπ(π))=Ξ¨π(Λπ₯(πβ1))(Λπ(π))=Λπ(π)(Λπ₯(πβ1))=β¦=Λπ₯(2)(Λπ(1))=Λπ₯(2)(π) when π is odd, and
Λπ(π+1)(Λπ₯(π))=Ξ¨π(Λπ(πβ1))(Λπ₯(π))=Λπ₯(π)(Λπ(πβ1))=β¦=π(1)(π₯)=π(π₯) when π is an even natural number. However, note that Λπ₯(2)(π) and π(π₯) are the same quantities in π½, the difference lies in the order of application of these linear functionals, which makes them the dual representation of each other.
Application to Fenchel conjugate
With this formalization, one can reason about the mathematical object, Fenchel conjugate in an elegant way. Let us first define what a Fenchel conjugate of a function is.
Fenchel conjugate - Let Vβ =β(V,π½) be the dual space of V, and β¨Β β
Β ,Β β
Β β© :Vβ ΓV βπ½ denote the dual pairing between the two vector spaces. For a function π :V βπ½ βͺ{βπ½}, its convex conjugate πβ :Vβ βπ½ βͺ{βπ½} is defined as
πβ(π)=supπ±βV{β¨π,π±β©βπ(π±)}βΒ πβVβ
For a differentiable function π :V βπ½, we have from the Taylorβs expansion that βπ(π±) is a linear functional for all π± βV, and therefore lies in the dual space Vβ. If πβ :Vβ βπ½ is the convex conjugate of π, we have that βπβ(π) is an element in Vββ for all π βVβ. Since there exists a natural isomorphism Ξ¨ :V βVββ between V and Vββ which is the evaluation map, this in particular gives us Ξ¨(π±) =Λπ± =βπβ(βπ(π±)) βVββ.