The determinant of a square matrix $A$ is typically defined in terms of cofactor expansion along the first row of $A$. Then cofactor expansion along other rows or along columns is defined, and shown (or stated) to be equal to the determinant. Following that, there is usually an example of a matrix that contains at least one zero. This example is used to illustrate that sometimes, if we choose the appropriate row or column to expand along (namely, one with zeros), we can reduce work needed to compute the determinant using cofactor expansion.
It is certainly easy to tell which row(s) or column(s) to expand along to minimize the number of cofactors it is necessary to compute at each step. Simply expand along a row or column that has the most zeros.
But what row or column should we expand along to minimize the total number cofactors to compute overall? Or, to put it in more practical terms, what row or column should we expand along to minimize the
amount of writing necessary?
Something to consider is that there are two ways to get a zero in
the cofactor expansion. If $B$ is some square submatrix encountered in the cofactor expansion of $A$, then either $b_{ij}=0$ or $\det B_{ij}=0$ ($B_{ij}$ being the $(i,j)-minor of $B$) to make a cofactor. Since determining whether or not
$\det B_{ij}=0$ requires a determinant computation, we would probably want to
know the answer to the question to answer the question, which leads to circular reasoning. So we'll assume that
we're basing our expansion minimization strategy purely on which entries
of $A$ are 0.
Of course, the answer to the question posed here is mostly useless for practical purposes, since nobody is going to compute the determinant through cofactor expansion for all but the smallest matrices.
But since we frequently present these example and pose these problems to students, with the expectation that they'll know what the best row or column is to expand along, I wonder if there's actually some way to tell what the best path to the determinant is from the matrix itself.
Monday, 4 November 2013
Thursday, 19 September 2013
A Few Questions Related to Planar Eulerian Graphs
Let $G$ be an Eulerian graph. Suppose there is some planar embedding of $G$ in the plane. When does $G$ have a "non-crossing" Eulerian cycle? That is to say, if there is a planar drawing of the graph, when can we find an Eulerian cycle in the graph that can be drawn along the edges of the planar drawing without crossing itself?
More generally, suppose that $G$ has $2t$ pairs of odd-degree vertices. It is known that the edges of $G$ can be decomposed into $t$ paths. When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?
Even more generally, suppose that $G$ has an embedding into a surface of genus $g$ (or non-orientable genus $g$). When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?
More generally, suppose that $G$ has $2t$ pairs of odd-degree vertices. It is known that the edges of $G$ can be decomposed into $t$ paths. When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?
Even more generally, suppose that $G$ has an embedding into a surface of genus $g$ (or non-orientable genus $g$). When is there a set of $t$ paths that decompose the edge set of the graph and that can be drawn without crossing themselves or each other?
Thursday, 12 September 2013
Planar Graph Drawing Problem
Suppose that $G$ is a planar graph. Define a convex representation of a graph to be an assignment of each vertex $v$ in $V(G)$ to a convex polygon $p(v)$ so that two vertices $u$ and $v$ are adjacent if and only if $p(u)$ and $p(v)$ intersect only on their boundaries in at least one edge (i.e. so that the polygons share more than just vertices, but the area of their intersection is zero). Furthermore, suppose that each vertex $v$ in $V(G)$ is assigned some positive number $f(v)$.
Does there exist a convex representation of $G$ so that the area of polygon $p(v)$ is equal to $f(v)$ for all $v$ in $V(G)$?
If $G$ is not 3-connected, then the answer is no, since a graph has a convex representation if and only if $G$ is 3-connected. An algorithm due to Tutte, applied to the dual graph, will find a convex representation, though it might not be aesthetically pleasing.
Based on the number of area cartograms that have popped up lately, it seems that representation of the graph by polygons with specified areas is also possible, if not all of the time, then most of the time (I've never seen a theorem to that effect, though it does seem plausible).
What asking for, then, is the intersection of both of these ideas. Like the Tutte embedding, the representation should be convex. Like the area embedding, the areas of each polygon should have the same size.
Does there exist a convex representation of $G$ so that the area of polygon $p(v)$ is equal to $f(v)$ for all $v$ in $V(G)$?
If $G$ is not 3-connected, then the answer is no, since a graph has a convex representation if and only if $G$ is 3-connected. An algorithm due to Tutte, applied to the dual graph, will find a convex representation, though it might not be aesthetically pleasing.
Based on the number of area cartograms that have popped up lately, it seems that representation of the graph by polygons with specified areas is also possible, if not all of the time, then most of the time (I've never seen a theorem to that effect, though it does seem plausible).
What asking for, then, is the intersection of both of these ideas. Like the Tutte embedding, the representation should be convex. Like the area embedding, the areas of each polygon should have the same size.
Sunday, 4 August 2013
Variable x, Ex-variable.
Is the variable $x$ still a variable once a value has been assigned to it? Because then, $x$ is fixed at the assigned value and can no longer vary, and that which cannot vary is not variable.
Saturday, 3 August 2013
Coefficient Operation
The trace of a matrix satisfies the following equation
$$tr(A+B)=tr(A)+tr(B)$$
The trace is also the coefficient of the second highest power of the characteristic polynomial (up to a factor of $-1$).
The determinant of a matrix satisfies the following equation
$$det(AB)=det(A)det(B)$$
The determinant is also the constant term of the characteristic polynomial (up to a factor of $-1$).
Thus, for both the trace and the determinant functions, there is a binary operation that is defined for both matrices and numbers, and the functions distribute over the corresponding binary operations. Furthermore, both functions appear in the characteristic polynomial.
If the matrix is 3x3 or larger, then there are many coefficients between that of the determinant and that the second highest power. We can think of these as generalizations of the trace and determinant.
That is, suppose that $f_k(A)$ is the coefficient of $\lambda^k$ in the characteristic polynomial $p(\lambda)$ of the $n\times n$ matrix $A$. Then $tr(A)=f_{n-1}(A)$ and $det(A)=f_0(A)$.
That leads to the following question. For each of the $k$, does there exist a binary operation, say $\circ_k$, that is defined for both square matrices and numbers such that $f_k(A\circ_k B)=f_k(A)\circ_k f_k(B)$ (up to a factor of $-1$)? Note that we want $A\circ_k B$ to be a matrix and $a\circ_k b$ to be a number.
We can take $\circ_{n-1}$ to be the trace function and $\circ_0$ to be the determinant function, so the answer is yes for $k=n-1$ and $k=0$.
The coefficient of $\lambda^n$ is always $\pm 1$. Define $\circ$ by $a\circ b=1$ and $A\circ B=I$. Then $f_n(A\circ B)=f_n(I)=1$ and $f_n(A)\circ f_n(B)=1\circ 1=1$. Thus,
$$f_n(A\circ B)=f_n(A)\circ f_n(B)$$
So we could take $\circ_n$ to be the binary operation $\circ$ defined here. So the answer is yes for $k=n$ as well. Note that $a\circ b$ must be defined to be 1 in order to satisfy the desired property, but $A\circ B$ could be defined to be any matrix, since $f_n$ is always $\pm 1$.
What can be said about $\circ_k$ for $k\in\{1,\ldots,n-2\}$?
There was some freedom in how we defined $\circ_n$. It is not unique. Is this true about the other $\circ_k$, if they even exist?
$$tr(A+B)=tr(A)+tr(B)$$
The trace is also the coefficient of the second highest power of the characteristic polynomial (up to a factor of $-1$).
The determinant of a matrix satisfies the following equation
$$det(AB)=det(A)det(B)$$
The determinant is also the constant term of the characteristic polynomial (up to a factor of $-1$).
Thus, for both the trace and the determinant functions, there is a binary operation that is defined for both matrices and numbers, and the functions distribute over the corresponding binary operations. Furthermore, both functions appear in the characteristic polynomial.
If the matrix is 3x3 or larger, then there are many coefficients between that of the determinant and that the second highest power. We can think of these as generalizations of the trace and determinant.
That is, suppose that $f_k(A)$ is the coefficient of $\lambda^k$ in the characteristic polynomial $p(\lambda)$ of the $n\times n$ matrix $A$. Then $tr(A)=f_{n-1}(A)$ and $det(A)=f_0(A)$.
That leads to the following question. For each of the $k$, does there exist a binary operation, say $\circ_k$, that is defined for both square matrices and numbers such that $f_k(A\circ_k B)=f_k(A)\circ_k f_k(B)$ (up to a factor of $-1$)? Note that we want $A\circ_k B$ to be a matrix and $a\circ_k b$ to be a number.
We can take $\circ_{n-1}$ to be the trace function and $\circ_0$ to be the determinant function, so the answer is yes for $k=n-1$ and $k=0$.
The coefficient of $\lambda^n$ is always $\pm 1$. Define $\circ$ by $a\circ b=1$ and $A\circ B=I$. Then $f_n(A\circ B)=f_n(I)=1$ and $f_n(A)\circ f_n(B)=1\circ 1=1$. Thus,
$$f_n(A\circ B)=f_n(A)\circ f_n(B)$$
So we could take $\circ_n$ to be the binary operation $\circ$ defined here. So the answer is yes for $k=n$ as well. Note that $a\circ b$ must be defined to be 1 in order to satisfy the desired property, but $A\circ B$ could be defined to be any matrix, since $f_n$ is always $\pm 1$.
What can be said about $\circ_k$ for $k\in\{1,\ldots,n-2\}$?
There was some freedom in how we defined $\circ_n$. It is not unique. Is this true about the other $\circ_k$, if they even exist?
Sunday, 28 July 2013
Two Videos
A friend sent me the following video today, inspired by a child's toy.
I've come across similar statements about things being "countless", and also cocked an eyebrow when I heard them. For example, I once read that postal codes were unlimited as well, when there are, in fact, only 17,576,000 different possibilities, roughly half of the number of people in Canada. In any case, it never occurred to me that such dubious claims (well, dubious to the mathematically trained) could be turned into lessons. It's quite remarkable just how interested the students got in the problem. This video, enticingly titled "998,001 and its Mysterious Recurring Decimals", showed up as one of the recommended videos in the sidebar.
The topic of this video would make an interesting diversion in a course on infinite series, and like the previous video, it has something of a combinatorial flavour.
I've come across similar statements about things being "countless", and also cocked an eyebrow when I heard them. For example, I once read that postal codes were unlimited as well, when there are, in fact, only 17,576,000 different possibilities, roughly half of the number of people in Canada. In any case, it never occurred to me that such dubious claims (well, dubious to the mathematically trained) could be turned into lessons. It's quite remarkable just how interested the students got in the problem. This video, enticingly titled "998,001 and its Mysterious Recurring Decimals", showed up as one of the recommended videos in the sidebar.
Wednesday, 17 July 2013
David Gregory
[Updated: see below]
On Thursday afternoon, I received an email from one of my colleagues that my former supervisor David Gregory's cancer had progressed and that he was in palliative care. I originally planned on visiting him the next day on Friday. However, I ended up spending most of the day finishing up a job application that was due shortly, and the tone of the email did not suggest the situation that was that dire. I had commitments on the weekend, so I put off the visit until Monday. On Monday morning, though, I received an email from Kevin Vander Meulen, friend, fellow collaborator, and also former student of David, who had found his obituary:
The first time I had seen David speak was when he gave a guest lecture on the Good Will Hunting Problem to my undergraduate graph theory class. Although I would not meet him until a few years later, I worked with David for the first time in the spring/summer of 1999 between the 3rd and 4th years of my undergraduate studies on the problem of addressing the Petersen Graph, the graph after which this blog is named. I would collaborate with him again the following summer.
It wasn't until the fall of 2001, when I had started my master's degree at Queen's University, that I met him for the first time. He was already retired then, after his first bout with cancer. Although he was still clearly recovering from his treatment, he would still regularly come into his office to work on his research.
After that, I didn't speak with him again until my original supervisor, Dom de Caen, had passed away in the spring of 2002. Even though he was already retired, David happily accepted me as his master's student, and later as his PhD student.
David was very dedicated as a supervisor. We met at least once a week, sometimes briefly, and sometimes for a whole afternoon. If I had questions outside of our regularly scheduled meetings, he was always happy to make time to discuss them with me, even if I just showed up at his door. When I reflect on the quality of the first draft of my master's project, I can't help but conclude that he was a very patient man. He helped me to turn what was a very rough draft into the final draft, without ever letting on that I had burdened him in any way. He demonstrated the same patience and dedication throughout my PhD studies as well, being available early in the morning as well as sending me helpful emails late in the evening.
David was a regular participant in the Discrete Math Seminar held jointly between the respective departments at Queen's University and the Royal Military College, which I frequently attended. His talks were always interesting, well organized, and easy to follow.
In addition to his role as a supervisor, he was also a good friend, giving me advice on personal matters and helping in other ways.
He will be missed.
-----
A memorial page has been set up by Bryan Shader, one of David's friends and collaborators.
On Thursday afternoon, I received an email from one of my colleagues that my former supervisor David Gregory's cancer had progressed and that he was in palliative care. I originally planned on visiting him the next day on Friday. However, I ended up spending most of the day finishing up a job application that was due shortly, and the tone of the email did not suggest the situation that was that dire. I had commitments on the weekend, so I put off the visit until Monday. On Monday morning, though, I received an email from Kevin Vander Meulen, friend, fellow collaborator, and also former student of David, who had found his obituary:
GREGORY, David - David Gregory of Kingston, Ontario passed away peacefully on Friday July 12, 2013 with friends and family by his side. He is predeceased by his parents Alan and Edith (Towell) Gregory. He is survived by his sister Betty Jane Lerer (Gregory) and his brother-in-law Harvey Lerer. As well he is survived by his nephew Michael Lerer, his niece Tara Lerer (Middleton) and great-nephew David Lerer. The family wants to thank his many friends and colleagues for their care and sympathy throughout his illness. A private funeral is arranged. A memorial celebration of David's life will be held in the near future. In lieu of flowers, donations to The Canadian Cancer Society or the University Hospitals Kingston Foundation would be preferred.Even if I had gone on Friday, it might have already been too late.
The first time I had seen David speak was when he gave a guest lecture on the Good Will Hunting Problem to my undergraduate graph theory class. Although I would not meet him until a few years later, I worked with David for the first time in the spring/summer of 1999 between the 3rd and 4th years of my undergraduate studies on the problem of addressing the Petersen Graph, the graph after which this blog is named. I would collaborate with him again the following summer.
It wasn't until the fall of 2001, when I had started my master's degree at Queen's University, that I met him for the first time. He was already retired then, after his first bout with cancer. Although he was still clearly recovering from his treatment, he would still regularly come into his office to work on his research.
After that, I didn't speak with him again until my original supervisor, Dom de Caen, had passed away in the spring of 2002. Even though he was already retired, David happily accepted me as his master's student, and later as his PhD student.
David was very dedicated as a supervisor. We met at least once a week, sometimes briefly, and sometimes for a whole afternoon. If I had questions outside of our regularly scheduled meetings, he was always happy to make time to discuss them with me, even if I just showed up at his door. When I reflect on the quality of the first draft of my master's project, I can't help but conclude that he was a very patient man. He helped me to turn what was a very rough draft into the final draft, without ever letting on that I had burdened him in any way. He demonstrated the same patience and dedication throughout my PhD studies as well, being available early in the morning as well as sending me helpful emails late in the evening.
David was a regular participant in the Discrete Math Seminar held jointly between the respective departments at Queen's University and the Royal Military College, which I frequently attended. His talks were always interesting, well organized, and easy to follow.
In addition to his role as a supervisor, he was also a good friend, giving me advice on personal matters and helping in other ways.
He will be missed.
-----
A memorial page has been set up by Bryan Shader, one of David's friends and collaborators.
Subscribe to:
Posts
(
Atom
)