Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading from a book (Combinatorial optimization by Schrijver) and at one point I am not clear as to how his arguments follow. Consider the following:

Let $G(V,E)$ be an undirected graph and let $w:E\rightarrow R_+$. For any subset $F$ of $E$, denote $w(F)=\sum_{e\in F}w(e)$. Denote the incidence vector of $F$ in $\mathbb{R}^E$ by $\chi^F$, i.e. for any edge $e$ in $E$, $\chi^F(e)=1$ if $e\in F$ and $\chi^F(e)=0$ otherwise. Considering $w$ as a vector in in $\mathbb{R}^E$ we have $w(F)=w^T\chi^F$.

My doubts are as follows:

  1. Is $E$ a vector space and $w,\chi^F$ linear transformations from $E$ to $\mathbb{R}$? Why are they referred to as vectors? Aren't they functions?
  2. What does the term incidence vector mean?
  3. How does it mathematically follow that $w(F)=w^T\chi^F$ ?
share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

1) Functions over finite sets may be equivalently thought of as vectors in the usual sense. Fix a finite set $E$, ordered arbitrarily as $E = \{ e_1, e_2, \ldots, e_m \}$. Then the set of functions $\mathcal F = \{ f : E \to \mathbb R \}$ is a real vector space of dimension $|E| = m$. In fact, this has the standard basis $\{ \delta_e \colon E \to \mathbb R \}_{e \in E}$ given by $$ \delta_e(e') = \begin{cases} 1, &e' = e, \\ 0, &e' \ne e. \end{cases} $$

Based on this idea alone, we are justified in calling a function $f : E \to \mathbb R$ a vector. After all, what are members of a vector space called, if not vectors? However, to cement the idea even more, we go a bit further. Imagine stacking up the values of the function $f$ as a column vector: $$ f = \left( \begin{array}{c} f(e_1) \\ f(e_2) \\ f(e_3) \\ \vdots \\ f(e_m) \end{array} \right). $$ Then what we get is a correspondence (an isomorphism, in fact) between the function space $\mathcal F$ and the more familiar space of $m$-dimensional column vectors. This "vector notation" is often preferred over the function representation, since it is more compact. Moreover, this works seamlessly in conjunction with matrices (and matrices are obviously important in linear algebra).


2) An incidence vector $\chi^F$ is essentially the characteristic function of the set $F \subseteq E$ -- seen as a vector. The characteristic function $\chi^F$ is defined as $$ \chi^F(e) = \begin{cases} 1, &e \in F, \\ 0, &e \notin F. \end{cases} $$ Correspondingly, we can write $\chi^F$ as the $m$-vector with $1$ in the $i^{th}$ position if $e_i \in F$, and $0$ otherwise.


3) Given two vectors $a$ and $b$, you might have seen the inner product between them, defined as $$ a^\mathrm T b = \sum_{i=1}^m a_i b_i. $$ Unfolding this to the function representation, we can define the inner product of two functions $f, g : E \to \mathbb R$ to be $$ \langle f, g \rangle = f^\mathrm T g = \sum_{e \in E} f(e) g(e). $$ In the special case when $f = w$ and $g = \chi^F$, we get $$ \langle w, \chi^F \rangle = w^\mathrm T \chi^F = \sum_{e \in E} w(e) \chi^F(e) = \sum_{e \in F} w(e), $$ which is $w(F)$ by definition.

share|improve this answer
add comment

"Vector" is sometime thought of as a sequence of values with indexed entries. This is one such example - the index set of $\chi^F$ is $E$, the set of edges.

Now here you can think of $\chi$ as an element of $\mathbb{R}^E$ in the sense that $\chi$ is a sequence of $|E|$ real numbers (0 or 1). Actually, in mathematics the symbol $A^B$ usually means "the set of functions from B to A" and $\mathbb{R}^n$ (your basic everyday vector space) can be thought of as a space of functions from $\{1,\dots,n\}$ to $\mathbb{R}$. Such a way of thinking is quite common in mathematics.

The name "incidence vector" means that the vector $\chi^F$ describes the meetings of the edges and the elements of $F$. There is also "incidence matrix" whose rows are vertices and columns edges with 1 for every pair of edge and vertex which meet.

$w(F)=w^T\chi^F$ is easy enough to see from the definitions here: by definition of vector multiplication (the usual scalar product), $w^T\chi^F=\sum_{e\in E}w(e)\chi^F(e)$, and since $\chi^F$ is either 0 or 1, and 1 exactly on $e\in F$, we get $\sum_{e\in E}w(e)\chi^F(e)=\sum_{e\in F}w(e)=w(F)$.

share|improve this answer
add comment

Let vi = (#i,yi), • • • ,vn = (xn,yn) be n two-dimensional vectors, where each Xi and each y¿ is an integer whose absolute valué does not exceed 2™/2/(i00v /ñ). Show that there are two disjoint sets I,J C {1,2,..., n} such that ! > = $ > ; • iei jeJ

share|improve this answer
1  
What you have typed is not rendering properly. –  Shahab Nov 19 '12 at 12:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.