"You've got to look at the situation here like any other situation where they've had a losing program," Walker said recently via phone while en route to meet with boosters in Albuquerque. "It takes a group of guys to come in and really sit down and look over the situation and try to make the necessary changes to turn this into a winning program.
"It's not like it's never been done before. A lot teams have started with losing programs, then a special group of coaches come in and change it."
Kansas State had managed one winning seasons in 18 years before Bill Snyder's arrival in 1989. Four years later, the Wildcats started a streak of eight consecutive seasons of at least nine wins.
California had gone eight years without a winning season until Jeff Tedford took over before the 2002 season. The Bears haven't had a losing season since. Rutgers went eight years without a winning record and hadn't appeared in a bowl since 1978 when Greg Schiano took over in '01. Now, the Scarlet Knights have a four-year bowl streak.
Wake Forest managed two winning seasons in 12 years before Jim Grobe was hired in 2001. Five years later, the Deacons won the ACC championship. Buffalo had not posted more than three wins since joining the MAC in 1999. But in the third year under coach Turner Gill, the Bulls won the conference championship last season.
The task Walker faces would seem just as challenging as the one Snyder faced, more daunting than those inherited by Tedford, Schiano, Grobe and Gill, and steeper than the Organ Mountains just east of Las Cruces.
Each of the past eight coaches at New Mexico State finished their tenures with losing records. The Aggies have not appeared in a bowl since 1960, have posted just four winning records in the past 41 seasons and have managed three victories or fewer 21 times in that span. Adding to that futility is that New Mexico State has played in the Missouri Valley, Big West, Sun Belt and Western Athletic conferences – not exactly the most challenging leagues in college football.
Walker, who is one of seven black head coaches at a Football Bowl Subdivision program, knows all about rebuilding jobs.
He left the NFL's Washington Redskins in 2006 to take the defensive coordinator position at UCLA, which had ranked 113th and 106th in the nation in total defense the previous two seasons.
In its first season under Walker, the Bruins' defense allowed 150 fewer yards per game and 14 fewer points per game. UCLA never ranked worst than 47th in total defense in three seasons under Walker.
He demanded his players at UCLA work hard, pay attention to detail and take no shortcuts. He'll demand the same at New Mexico State, which allowed an average of 34.1 points per game last season.
"There is no question the formula we were able to come up with at UCLA is what we'll use here – not only with the defense, but for the entire football team," Walker said. "It's a matter of just not cutting corners, being very strategic in how you break down the defense and the entire team. The beauty of it is our players are buying into it. We're anxious to see if the formula works like it did at UCLA.
"We're trying to approach this like a big-time program because I think it is. You have to approach in this way or we won't win."
Walker is convinced New Mexico State can win, and he gleans encouragement from what some may think is a surprising source. Former basketball coach Reggie Theus took over a program that managed just six victories in 2005 and posted 41 wins in two seasons while leading the Aggies to the NCAA tournament in 2007.
That might seem like comparing apples and oranges, but Walker said Theus' success showed the potential to win in Las Cruces.
"I've had a couple of conversations with Reggie about his approach and some of the things he accomplished," Walker said. "I think we have similar approaches in just having confidence in your guys, working hard and showing the community you care. You have to bring all those entities together to present a championship attitude. I think we're on course to doing some of the same things he was able to do."
The football equivalent to what Theus accomplished would be ending that nearly half-century streak of failing to reach a bowl game.
"Once we win, you'll see a different town," he said of Las Cruces. "We'll show them we're passionate and we care for the community. This town is starving for a winner."
Providing a winner will likely require a significant upgrade in talent, which won't be easy.
In the past four years, only three New Mexico high school players have been rated three stars or higher by Rivals.com. None signed with the Aggies. New Mexico does border talent-rich Texas and Las Cruces is about 45 miles from El Paso. But that part of Texas doesn't typically turn out many prospects.
Yet Walker is undeterred.
"I think you have to get the best players in the state first," he said. "We have good players in the state. We definitely want to keep New Mexico players home.
"My strength is in California, and we'll definitely recruit hard in my comfort zone. We've got to do a good job in the Houston area, the Dallas area, and do a good job in Phoenix. We have coaches on staff with connections all around the country. If we can snag a kid from New Jersey or Colorado, we'll do that as well. And we also want to hit El Paso real hard. It's like it's almost part of Las Cruces in my mind."
Still, some might think Walker is out of his mind to believe New Mexico State can rise above the likes of Boise State, Hawaii, Fresno State and Nevada in the WAC. But skeptics once doubted coaches at Kansas State, California, Rutgers, Wake Forest and Buffalo, too.
This week's Edge was requested by reader Jason Baguley.
Each week, we'll match two teams to determine which has the edge in various categories. Got a matchup you want to see? Send in to firstname.lastname@example.org and we'll work on it.
1. Head to head
Michigan leads the series 3-2, but Oregon has won the past two meetings, including a 39-7 blowout of the Wolverines in 2007.
Michigan: The Wolverines are college football's all-time winningest program with 872 victories.
Oregon: The Ducks' all-time record is 558-464-46.
Michigan: The venerable maize-and-blue jerseys and winged helmets are perhaps the most identifiable uniform in college football.
Oregon: The Ducks mix and match game-day ensembles. It's been reported that the Ducks have 384 uniform combinations. Really.
4. Sitcom actors
Oregon: David Ogden Stiers (Maj. Charles Emerson Winchester on "M*A*S*H") and Howard Hesseman (Dr. Johnny Fever on "WKRP in Cincinnati") attended Oregon.
Michigan: Ann B. Davis (Alice on "The Brady Bunch").
5. Presidential ties
Oregon: Theodora Nathan, who received a B.A. in journalism from Oregon in 1971, was the first woman to receive an electoral vote in a U.S. presidential election, as the 1972 Libertarian candidate.
Michigan: Gerald Ford, a 1935 graduate of Michigan, became President of the United States in 1974. He was not elected, but that's another story.
Edge: Michigan. Ford lettered in football at Michigan from 1932-34. There are no records of Nathan playing football at Oregon.
6. Big-money donors
Michigan: Al Glick, the CEO of Arlo Steel, has made numerous generous contributions to Michigan's athletic department.
Oregon: Phil Knight, Nike co-founder and chairman, is an Oregon grad who reportedly has donated more than $200 million to the athletic department. An athletic building is named for him, and he has a locker in the football team locker room.
7. At the movies
Michigan: Almost all of the adult characters in "The Big Chill" attended Michigan, and in "Air Force One" Harrison Ford's character is a Michigan grad who doesn't want to be disturbed while watching the Michigan-Notre Dame game.
Oregon: "Animal House" was filmed at Oregon.
8. Shameless Heisman Trophy promotion
Michigan: Desmond Howard struck the Heisman Trophy pose after a 93-yard punt return against Ohio State in 1991.
Oregon: Ten years after Howard's pose, Oregon boosters shelled out $250,000 to hype quarterback Joey Harrington as "Joey Heisman" on a billboard in New York City's Times Square.
Edge: Michigan. Howard won the Heisman. Harrington finished fourth in 2001.
9. Spread offense
Michigan: Coach Rich Rodriguez's version of the spread produced some powerful rushing offenses at West Virginia, but last season, Michigan averaged just more than147 rushing yards per game to rank 59th in the nation.
Oregon: When Oregon's newly promoted coach Chip Kelly was offensive coordinator at New Hampshire, the Wildcats averaged more than 400 yards in seven of eight seasons. In two seasons as offensive coordinator at Oregon, the Ducks ranked second and sixth in the nation in rushing offense.
Edge: Oregon. Running back LeGarrette Blount, who rushed for more than 1,000 yards, and quarterback Jeremiah Masoli return. Michigan will have a new quarterback. Top rusher Brandon Minor is back, but gained only 533 yards in '08.
From Patrick Istorico, from Birmingham, Ala.: Nobody beats John Wayne? (The Edge: USC vs. Florida State, March 18). Fair enough, but I don't think you gave Burt Reynolds enough credit for his role as Jack Horner in "Boogie Nights." Let's also remember that USC had its fingerprints (no pun intended) all over the "Naked Gun" films.
Olin Buchanan is the senior college football writer for Rivals.com. He can be reached at email@example.com.